3.3 Kruskal 算法

这一篇继续贪心，进入图的世界——最小生成树（Minimum Spanning Tree，MST）。Kruskal 算法是求 MST 的两大经典之一（另一个是 Prim，思路相近），它把贪心和第一卷的并查集（第六卷 6.2 会详讲，这里先用）结合得天衣无缝。

1.问题：用最少的边把所有点连通

给一个连通无向图 $G=(V,E)$ ，每条边有权重。最小生成树是一棵覆盖所有顶点的树（ $|V|-1$ 条边、无环、连通），且边权总和最小。

直觉：要把 $n$ 个城市用公路连通（任意两城可达），想让修路总成本最低。MST 就是这个"最省的连通方案"。

注意"树"的两个约束：恰好 $|V|-1$ 条边（再多就有环、再少就不连通）、连通。MST 是在所有满足这两个约束的子图里，边权和最小的。

2.Kruskal 的贪心：从小到大加边，不形成环就收

Kruskal 的贪心准则极其直白：把所有边按权重从小到大排序，依次考虑每条边——只要它不和你已选的边形成环，就选它。 选够 $|V|-1$ 条边就停。

KRUSKAL(G)
    把 E 按权重升序排序
    MST = ∅
    for 每条边 (u,v) in E（已排序）:
        if u 和 v 不在同一连通分量（加这条边不形成环）:
            MST = MST ∪ {(u,v)}
            合并 u、v 所在的连通分量
    return MST

一遍扫描边，排序 $O(E\log E)$ 。判断"成不成环"靠并查集（下文讲），所以整体 $O(E\log E)$ 。

3.关键工具：并查集高效判环

"加这条边会不会形成环"——这个判断，朴素法是每次 DFS 检查， $O(V+E)$ 太慢。Kruskal 的聪明之处在于用并查集（union-find）让它接近 $O(1)$ 。

并查集维护一堆元素分组，支持两个操作：

FIND(x)：x 属于哪个组（哪个连通分量）。
UNION(x,y)：把 x、y 所在的两组合并。

判环就变成：FIND(u) == FIND(v) 吗？若 u、v 已在同一组（同连通分量），加这条边就会形成环，跳过；否则选这条边，UNION(u,v) 合并两组。

并查集配两个优化（路径压缩 + 按秩合并），单次操作近乎 $O(1)$ （准确说是反阿克曼函数 $\alpha$ ，增长极慢）。这让 Kruskal 的判环极其高效。第六卷 6.2 会深讲并查集，现在你记住它把"动态连通性"维护成近乎常数即可。

4.为什么对：贪心选择性质 + 切割性质

Kruskal 正确性的核心是切割性质（cut property）：

对图的任意一个切割（把顶点分成 S 和 V−S 两拨），横跨切割的最短边，一定属于某个 MST。

Kruskal 每次加最短的不成环边，本质就是在反复用切割性质：当前选的边，相当于某个切割的最短跨边，它必在 MST 中。第四卷会给严格证明，这里抓住直觉——最短跨边如果不选，就得选更长的边跨过去，总权和更大，所以最短跨边一定在最优解里。

注意贪心选择性质也成立：每次加的边都是 MST 的一部分，无需回头。这保证了贪心一路对到底。

5.Kruskal vs Prim：两种 MST 贪心

求 MST 还有另一个经典贪心——Prim 算法。它从任意起点出发，每次把"与当前树相邻、权重最小的边"加入，逐步长成一棵树。

	Kruskal	Prim
贪心准则	全局最短的不成环边	与当前树相邻的最短边
数据结构	并查集	优先队列（堆）
适合	稀疏图（边少）	稠密图（边多）
复杂度	$O(E\log E)$	$O(E\log V)$

两者都是贪心，都靠切割性质保证正确，只是加边的顺序和数据结构不同。工程上稀疏图（如网络、社交关系）爱用 Kruskal，稠密图爱用 Prim。

6.练习

Q1. 给一个 4 顶点图，边权为 (1,2):1, (2,3):2, (3,4):3, (1,4):10, (2,4):5，写出 Kruskal 的执行过程。

边排序：(1,2):1, (2,3):2, (3,4):3, (2,4):5, (1,4):10。加 (1,2)：不环，选；加 (2,3)：不环，选；加 (3,4)：不环，选。已选 3 条 = |V|-1，停。MST = {(1,2),(2,3),(3,4)}，总权 6。后面的 (2,4)、(1,4) 都不看了（已够 $|V|-1$ 条）。

Q2. 并查集怎么帮 Kruskal 高效判断"加这条边会不会形成环"？

并查集维护每个顶点所属的连通分量。加边 (u,v) 前，查 FIND(u) 和 FIND(v)：若相同，说明 u、v 已连通，加这条边会成环，跳过；若不同，选这条边并 UNION(u,v) 合并两分量。配路径压缩 + 按秩合并，单次近乎 $O(1)$ ，远快于每次 DFS 判环。

Q3.（思考题） Kruskal 和 Prim 都是贪心求 MST，分别适合什么图？为什么？

Kruskal（全局最短不成环边 + 并查集， $O(E\log E)$ ）适合稀疏图——边少时排序和并查集都轻量。Prim（与当前树相邻最短边 + 堆， $O(E\log V)$ ）适合稠密图——它不用全局排序所有边，只维护相邻边，边多时更省。两者都靠切割性质保证正确，差别在数据结构对不同图密度的适配。

7.小结

Kruskal 用"按权重升序加边、不成环就收"的贪心，配合并查集高效判环， $O(E\log E)$ 求出最小生成树。正确性靠切割性质（最短跨边必在 MST）。它和 Prim 是 MST 的两大贪心，分别适配稀疏/稠密图。下一篇我们继续贪心，讲最短路的 Dijkstra——它引入"松弛"这个图算法的核心操作。