Java实现Kruskal算法
Kruskal算法是一种用于查找无向图最小生成树的贪心算法,下面我将提供一个完整的Java实现。
（图片来源网络，侵删）
- 将所有边按权重从小到大排序
- 初始化一个空的生成树
- 遍历排序后的边,如果加入该边不会形成环，则将其加入生成树
- 重复步骤3直到生成树包含所有顶点
Java实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
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;
}
@Override
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
class Subset {
int parent, rank;
}
public class KruskalAlgorithm {
private int V; // 顶点数量
private List<Edge> edges;
public KruskalAlgorithm(int V) {
this.V = V;
this.edges = new ArrayList<>();
}
public void addEdge(int src, int dest, int weight) {
edges.add(new Edge(src, dest, weight));
}
private int find(Subset[] subsets, int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
private void union(Subset[] subsets, int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
public void kruskalMST() {
List<Edge> result = new ArrayList<>();
Collections.sort(edges);
Subset[] subsets = new Subset[V];
for (int i = 0; i < V; ++i) {
subsets[i] = new Subset();
subsets[i].parent = i;
subsets[i].rank = 0;
}
int e = 0; // 已添加的边数
int i = 0; // 当前处理的边索引
while (e < V - 1 && i < edges.size()) {
Edge nextEdge = edges.get(i++);
int x = find(subsets, nextEdge.src);
int y = find(subsets, nextEdge.dest);
if (x != y) {
result.add(nextEdge);
union(subsets, x, y);
e++;
}
}
// 打印结果
System.out.println("Edges in the constructed MST:");
for (Edge edge : result) {
System.out.println(edge.src + " -- " + edge.dest + " == " + edge.weight);
}
}
public static void main(String[] args) {
int V = 4; // 顶点数量
KruskalAlgorithm graph = new KruskalAlgorithm(V);
// 添加边 (src, dest, weight)
graph.addEdge(0, 1, 10);
graph.addEdge(0, 2, 6);
graph.addEdge(0, 3, 5);
graph.addEdge(1, 3, 15);
graph.addEdge(2, 3, 4);
graph.kruskalMST();
}
}
代码说明
-
Edge类：表示图中的边，包含源顶点、目标顶点和权重，实现了Comparable接口以便排序。
-
Subset类：用于并查集(Union-Find)数据结构，帮助检测环。
-
KruskalAlgorithm类：
addEdge()方法：向图中添加边find()方法：使用路径压缩的查找操作union()方法：使用按秩合并的联合操作kruskalMST()方法：实现Kruskal算法主逻辑
-
主方法：创建一个示例图并运行Kruskal算法。
（图片来源网络，侵删）
复杂度分析
- 时间复杂度：O(E log E)，其中E是边数，主要来自排序操作
- 空间复杂度：O(V + E)，用于存储边和并查集结构
示例输出
对于给定的示例图,输出将是：
Edges in the constructed MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10这表示最小生成树由这三条边组成,总权重为19。
（图片来源网络，侵删）
