Kruskal 算法求最小/最大生成树及 Java 实现

1. 概述

在之前的文章中，我们介绍了使用 Prim 算法求最小生成树。本文将采用另一种经典思路——Kruskal 算法，来解决最小生成树（Minimum Spanning Tree, MST）和最大生成树问题。

相比 Prim 算法的“逐步扩张”策略，Kruskal 更像是“挑三拣四”：按权重从小到大选边，只要不形成环就加进来，直到凑够 V-1 条边为止。思路简单粗暴，但背后的数据结构设计却非常巧妙。

2. 生成树基础概念

生成树（Spanning Tree） 是一个无向连通图的子图，它满足两个条件：

✅ 包含图中所有顶点
✅ 边数最少且无环（即形成一棵树）

一个图可能有多个生成树。如下图所示，红色边构成了一棵生成树：

当图是带权图时，生成树的权重定义为所有边权之和。那么：

✅ 最小生成树（MST）：权重最小的生成树
✅ 最大生成树：权重最大的生成树

下图展示了一个带权图的最小生成树：

而下图则是该图的最大生成树：

3. Kruskal 算法原理

Kruskal 算法的核心思想是贪心 + 并查集判环。对于一个有 V 个节点的图，其生成树必须恰好有 V-1 条边。

算法伪代码如下：

初始化空边集 T
将图中所有边按权重升序排序
遍历排序后的边列表：
    检查当前边加入 T 是否会形成环
    如果不会形成环，则将该边加入 T
    如果 T 已有 V-1 条边，结束循环
返回 T

我们以下图为例，逐步演示 Kruskal 构造最小生成树的过程：

选最小边 (0,2)，权重 2，加入 ✅
加入 (3,4) 和 (0,1)，均无环 ✅
尝试加入 (1,2)，权重 9，但会形成环 (0→1→2→0)，跳过 ❌
最后加入 (2,4)，权重 10，完成 MST ✅

💡 最大生成树？ 只需将边按权重降序排序即可，其余逻辑完全一致。

构造最大生成树的过程如下图所示：

4. 使用并查集进行环检测

Kruskal 算法的关键在于高效判断“加入某条边是否会成环”。虽然可以用 DFS 判断，但每次都要遍历，效率低。

✅ 最优解：并查集（Union-Find）
它天然支持“动态连通性”查询，完美契合 Kruskal 的边增量添加模式。

4.1 并查集与生成树构建

初始时，每个节点自成一个集合。处理每条边 (u, v) 时：

若 find(u) == find(v) → 同集合，加边必成环 ❌
否则 → 不同集合，union(u, v) 合并，并加入该边 ✅

以最小生成树为例，初始集合：{0}, {1}, {2}, {3}, {4}

处理 (0,2)：不同集合 → 合并为 {0,2}，加边 ✅
处理 (3,4)：合并为 {3,4} ✅
处理 (0,1)：合并为 {0,1,2} ✅
处理 (1,2)：find(1)=find(2) → 同集合，跳过 ❌
处理 (2,4)：{0,1,2} 与 {3,4} 不同 → 合并，加边 ✅

最终得到完整生成树。

4.2 并查集数据结构实现

我们用树形结构表示每个集合，每个节点指向其父节点，根节点的父节点指向自己。

public class DisjointSetInfo {
    private Integer parentNode;
    private int rank;

    DisjointSetInfo(Integer parent) {
        setParentNode(parent);
        setRank(0);
    }

    // standard setters and getters
}

用 List<DisjointSetInfo> 存储所有节点的并查集信息，索引即节点编号：

void initDisjointSets(int totalNodes) {
    nodes = new ArrayList<>(totalNodes);
    for (int i = 0; i < totalNodes; i++) {
        nodes.add(new DisjointSetInfo(i));
    }
}

4.3 查找操作（Find）与路径压缩

朴素查找：

Integer find(Integer node) {
    Integer parent = nodes.get(node).getParentNode();
    if (parent.equals(node)) {
        return node;
    } else {
        return find(parent);
    }
}

⚠️ 问题：可能形成链式结构，退化为 O(n)。

✅ 优化：路径压缩（Path Compression）
递归返回时，将沿途节点直接挂到根节点下，大幅缩短后续查找路径。

Integer pathCompressionFind(Integer node) {
    DisjointSetInfo setInfo = nodes.get(node);
    Integer parent = setInfo.getParentNode();
    if (parent.equals(node)) {
        return node;
    } else {
        Integer root = pathCompressionFind(parent);
        setInfo.setParentNode(root);
        return root;
    }
}

4.4 合并操作（Union）与按秩合并

朴素合并：

void union(Integer rootU, Integer rootV) {
    nodes.get(rootU).setParentNode(rootV);
}

⚠️ 问题：随意合并可能导致树越来越深，影响 find 性能。

✅ 优化：按秩合并（Union by Rank）
将秩（近似树高）小的树挂到秩大的树下。仅当秩相等时，合并后秩才 +1。

void unionByRank(int rootU, int rootV) {
    DisjointSetInfo setInfoU = nodes.get(rootU);
    DisjointSetInfo setInfoV = nodes.get(rootV);
    int rankU = setInfoU.getRank();
    int rankV = setInfoV.getRank();

    if (rankU < rankV) {
        setInfoU.setParentNode(rootV);
    } else {
        setInfoV.setParentNode(rootU);
        if (rankU == rankV) {
            setInfoU.setRank(rankU + 1);
        }
    }
}

4.5 环检测实现

结合路径压缩和按秩合并，环检测代码简洁高效：

boolean detectCycle(Integer u, Integer v) {
    Integer rootU = pathCompressionFind(u);
    Integer rootV = pathCompressionFind(v);

    if (rootU.equals(rootV)) {
        return true; // 成环
    }

    unionByRank(rootU, rootV);
    return false; // 无环，已合并
}

⚡ 性能分析：
单次 find 或 union 操作的均摊时间复杂度为 **O(α(V))**，其中 α 是反阿克曼函数，在实际应用中可视为常数（< 5）。这是并查集高效的精髓所在。

5. Java 实现 Kruskal 算法

我们使用 Google Guava 库中的 ValueGraph 来表示带权无向图，它对图操作支持良好。

首先引入 Guava 依赖：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>33.0.0-jre</version>
</dependency>

将并查集封装为 CycleDetector 类，然后实现通用的生成树构造函数：

ValueGraph<Integer, Double> spanningTree(ValueGraph<Integer, Double> graph, boolean minSpanningTree) {
    Set<EndpointPair<Integer>> edges = graph.edges();
    List<EndpointPair<Integer>> edgeList = new ArrayList<>(edges);

    if (minSpanningTree) {
        edgeList.sort(Comparator.comparing(e -> graph.edgeValue(e).get()));
    } else {
        edgeList.sort(Collections.reverseOrder(Comparator.comparing(e -> graph.edgeValue(e).get())));
    }

    int totalNodes = graph.nodes().size();
    CycleDetector cycleDetector = new CycleDetector(totalNodes);
    int edgeCount = 0;

    MutableValueGraph<Integer, Double> spanningTree = ValueGraphBuilder.undirected().build();
    for (EndpointPair<Integer> edge : edgeList) {
        if (cycleDetector.detectCycle(edge.nodeU(), edge.nodeV())) {
            continue; // 成环，跳过
        }
        spanningTree.putEdgeValue(edge.nodeU(), edge.nodeV(), graph.edgeValue(edge).get());
        edgeCount++;
        if (edgeCount == totalNodes - 1) {
            break; // 边数够了，提前退出
        }
    }
    return spanningTree;
}

💡 时间复杂度分析：

排序边：O(E log E)

遍历边 + 并查集操作：O(E α(V)) ≈ O(E)

总体：O(E log E)
由于 E 最多为 O(V²)，log E ≈ log V，也可写作 O(E log V)

6. 总结

Kruskal 算法以贪心策略为核心，借助并查集高效判环，实现了简洁而高效的最小/最大生成树求解。

✅ 优点：逻辑清晰，易于实现，适合稀疏图
✅ 关键点：并查集的路径压缩 + 按秩合并，是性能保障
✅ 扩展：稍改排序方式即可支持最大生成树

本文完整代码已托管至 GitHub：https://github.com/tech-tutorial-examples/kruskal-demo

Persistence

REST

Security