Kruskal
Kruskal
Kruskal 算法是一种基于贪心策略的最小生成树算法，它通过逐步选择权重最小的边，并确保该边不会形成环路来构建最小生成树。
算法流程如下：
- 创建一个空的最小生成树 MST 和一个空的集合 visited，用于存放已经访问过的顶点。
- 将图中的所有边按照权重从小到大进行排序。
- 遍历排序后的边，对于每条边 (u, v)：
- 如果加入边 (u, v) 后不会形成环路，则将该边加入 MST，并将顶点 u 和顶点 v 加入 visited 集合中。
- 如果加入边 (u, v) 后形成环路，则忽略该边。
- 重复步骤 3，直到 MST 中包含 n-1 条边，最终得到的 MST 就是最小生成树。
java 模板如下：
static class Edge implements Comparable<Edge> {
int src, dest, weight;
public Edge(int src, int dest, int weight){
this.src = src;
this.dest = dest;
this.weight = weight;
}
public int compareTo(Edge edge) {
return this.weight - edge.weight;
}
}
static int[][] kruskalMST(Edge[] edges, int V) {
int[][] mst = new int[V][V]; // 最小生成树
int E = edges.length; // 边数
Arrays.sort(edges);
// 使用并查集判断是否存在回路
int[] parent = init(V);
int edgeCount = 0; // 记录加入最小生成树的边数
int index = 0; // 边数组的索引
// 构建最小生成树
while (edgeCount < V - 1 && index < E) {
Edge nextEdge = edges[index++];
int x = find(parent, nextEdge.src);
int y = find(parent, nextEdge.dest);
if (x != y) {
mst[nextEdge.src][nextEdge.dest] = nextEdge.weight;
mst[nextEdge.dest][nextEdge.src] = nextEdge.weight;
edgeCount++;
union(parent, x, y);
}
}
return mst;
}
// 并查集
static int[] init(int n){
int[] parent = new int[n]; // 用于判断是否形成环路
for (int i = 0; i < n; i++) {
parent[i] = i;
}
return parent;
}
static int find(int[] parent, int i) {
if (parent[i] != i) {
parent[i] = find(parent, parent[i]);
}
return parent[i];
}
static void union(int[] parent, int x, int y) {
int xroot = find(parent, x);
int yroot = find(parent, y);
parent[yroot] = xroot;
}