Kruskal算法详解（Java语言实现最小生成树的完整教程）

Kruskal算法的关键技术点

• 边排序：将所有边按权重从小到大排序。
• 并查集（Union-Find）：用于高效判断添加某条边是否会形成环。
• 贪心策略：每次都选当前最小权重的可行边。

Java实现步骤详解

下面我们分步实现Kruskal算法。

1. 定义边类 Edge

class Edge {    int src, dest, weight;    public Edge(int src, int dest, int weight) {        this.src = src;        this.dest = dest;        this.weight = weight;    }}

2. 实现并查集 UnionFind

class UnionFind {    private int[] parent;    private int[] rank;    public UnionFind(int n) {        parent = new int[n];        rank = new int[n];        for (int i = 0; i < n; i++) {            parent[i] = i;            rank[i] = 0;        }    }    public int find(int x) {        if (parent[x] != x) {            parent[x] = find(parent[x]); // 路径压缩        }        return parent[x];    }    public void union(int x, int y) {        int rootX = find(x);        int rootY = find(y);        if (rootX != rootY) {            // 按秩合并            if (rank[rootX] < rank[rootY]) {                parent[rootX] = rootY;            } else if (rank[rootX] > rank[rootY]) {                parent[rootY] = rootX;            } else {                parent[rootY] = rootX;                rank[rootX]++;            }        }    }}

3. 主算法：Kruskal

import java.util.*;public class KruskalMST {    public static List<Edge> kruskalMST(int vertices, List<Edge> edges) {        // 按权重升序排序        Collections.sort(edges, (a, b) -> a.weight - b.weight);        UnionFind uf = new UnionFind(vertices);        List<Edge> mst = new ArrayList<>();        for (Edge edge : edges) {            int rootSrc = uf.find(edge.src);            int rootDest = uf.find(edge.dest);            // 如果不在同一集合，说明不会成环            if (rootSrc != rootDest) {                mst.add(edge);                uf.union(rootSrc, rootDest);                // 最小生成树有 vertices - 1 条边                if (mst.size() == vertices - 1) break;            }        }        return mst;    }    public static void main(String[] args) {        int vertices = 4;        List<Edge> edges = new ArrayList<>();        edges.add(new Edge(0, 1, 10));        edges.add(new Edge(0, 2, 6));        edges.add(new Edge(0, 3, 5));        edges.add(new Edge(1, 3, 15));        edges.add(new Edge(2, 3, 4));        List<Edge> mst = kruskalMST(vertices, edges);        System.out.println("最小生成树的边：");        for (Edge e : mst) {            System.out.println(e.src + " -- " + e.dest + " == " + e.weight);        }    }}

运行结果说明

以上代码输出如下：

最小生成树的边：2 -- 3 == 40 -- 3 == 50 -- 1 == 10

这三条边构成了图的最小生成树，总权重为 4 + 5 + 10 = 19。

总结

通过本教程，你已经掌握了Kruskal算法的核心思想和Java实现Kruskal的完整过程。该算法时间复杂度主要由排序决定，为 O(E log E)，其中 E 是边的数量。它非常适合稀疏图（边较少）的最小生成树问题。

无论你是学习图论算法的新手，还是准备面试的开发者，Kruskal算法都是必须掌握的基础内容。动手敲一遍代码，加深理解吧！