prim算法求最小生成树
时间: 2023-07-06 18:02:41 浏览: 101
Prim算法是一种用于求解最小生成树(Minimum Spanning Tree,MST)的经典算法。它基于贪心策略,在一个加权连通图中,从一个起始顶点开始逐步扩展最小生成树,直到包含所有顶点。下面是Prim算法的一种常见实现:
初始化:
创建一个空的最小生成树集合MST,用于存储最终的最小生成树。
创建一个空的优先队列或最小堆,用于选择下一个要加入最小生成树的边。
随机选择一个起始顶点作为初始顶点。
标记起始顶点:
将起始顶点标记为已访问。
将起始顶点的所有边添加到优先队列或最小堆中。
扩展最小生成树:
当优先队列或最小堆不为空时,重复以下步骤:
从优先队列或最小堆中选择权重最小的边(u, v)。
如果顶点v未被访问:
将边(u, v)添加到最小生成树集合MST中。
标记顶点v为已访问。
将顶点v的所有边添加到优先队列或最小堆中。
输出最小生成树:
最终,MST中将包含连通图的最小生成树。
以下是一个Java示例代码,演示了如何使用Prim算法求解最小生成树:
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
class Edge implements Comparable<Edge> {
private int source;
private int destination;
private int weight;
public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
public int getSource() {
return source;
}
public int getDestination() {
return destination;
}
public int getWeight() {
return weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
public class PrimAlgorithm {
private int numVertices;
private List<List<Edge>> adjacencyList;
public PrimAlgorithm(int numVertices) {
this.numVertices = numVertices;
this.adjacencyList = new ArrayList<>();
for (int i = 0; i < numVertices; i++) {
adjacencyList.add(new ArrayList<>());
}
}
public void addEdge(int source, int destination, int weight) {
Edge edge = new Edge(source, destination, weight);
adjacencyList.get(source).add(edge);
adjacencyList.get(destination).add(edge);
}
public void primMST() {
boolean[] visited = new boolean[numVertices];
int[] parent = new int[numVertices];
int[] key = new int[numVertices];
for (int i = 0; i < numVertices; i++) {
key[i] = Integer.MAX_VALUE;
}
PriorityQueue<Edge> minHeap
阅读全文