目录
1. Kruskal 算法简介
Kruskal 算法用于构造最小生成树：给定一个连通的无向带权图，它挑选出总代价最小的一组边，使之覆盖所有顶点且不形成任何环。对于 V 个顶点，这组边恰好总是 V - 1 条。
Prim 算法是从一个起点出发、让单棵连通的树向外生长；而 Kruskal 直到最后一刻之前，几乎完全不理会连通性。它把图中所有边按权重排序，从最便宜的一路走到最贵的，只要某条边不会闭合成环就把它留下。除此之外不参考任何信息。既没有起始顶点，也没有“前沿”的概念。
其结果是，Kruskal 在运行过程中大部分时间握着的是一片森林而非一棵树：许多散落在图中的小碎片，各自独立地生长、合并，直到它接受的最后一条边才融合成一棵完整的生成树。正是这种形态上的差异，使它在稀疏图上、在非连通输入上、以及在性能分析器下的表现都与 Prim 不同。
2. 为什么它是对的：环性质
Prim 的正确性依托于一条关于哪些边可以安全接受的定理。Kruskal 则有同样多的时间花在拒绝边上，因此值得把那条为“丢弃”提供依据的姊妹定理也讲清楚。
环性质。对于图中的任意一个环，只要该环上权重最大的边严格重于环上其他所有边，那么它就不属于最小生成树。若有多条边并列最重，则其中至少一条可以被舍弃。
证明与割性质的证明互为镜像。假设某个环上最重的边 e 确实属于某棵最小生成树 T。把 e 从 T 中删去，T 会裂成两个连通块。该环的其余部分仍然横跨这两个连通块，因此环上必有另一条边 f 能把它们重新连通。改用 f，你便重新得到一棵生成树；而由于 e 严格最重，新树严格更轻，这与 T 是最小生成树相矛盾。
现在看 Kruskal 拒绝一条边时发生了什么。它走到边 e，发现两个端点已经处在同一个碎片中。这意味着它们之间早已存在一条路径，而这条路径完全由算法更早接受的边构成，也就是由不重于 e 的边构成。加入 e 会闭合出一个环，而 e 正是该环上最重的一条。依据环性质，丢弃它不会有任何损失。
被接受的边之所以安全，理由与 Prim 相同。当一条边连接两个不同碎片时，它就是横跨“该碎片与其余部分”这个割的最便宜的剩余边，割性质原封不动地适用。Kruskal 同时在两个方向上贪心，而这两个方向都是定理。
3. 森林是如何合并的
具体来说，算法一开始把每个顶点各自放进一个碎片：V 个碎片，零条边。在遍历排好序的边列表时，它对每条边 (u, v) 只问一个问题：
u与v是否已在同一碎片中？若是，这条边会闭合成环。丢弃它，继续下一条。- 它们是否位于不同碎片？若是，接受这条边，并把两个碎片合并为一个。
每接受一条边，碎片数恰好减少一个。从 V 个碎片走到只剩一个，意味着恰好 V - 1 次接受，这正是停止条件。一旦达到这个数目，列表中剩余的每条边都必然会被拒绝，因此循环可以提前退出。
于是整个算法归结为一个数据结构问题：如何在数百万次的调用中，快速回答“是否同一碎片？”与“把这两个碎片合并”？这恰好就是并查集所提供的能力。
4. 逐步执行演示
取我们最小生成树指南中一直使用的那个六顶点图。它的九条边是：
A-B 4 A-C 1 B-C 2
B-D 5 C-D 6 C-E 7
D-E 2 D-F 8 E-F 3按权重排序后，就得到算法实际会走的顺序：
A-C 1 B-C 2 D-E 2 E-F 3 A-B 4 B-D 5 C-D 6 C-E 7 D-F 8每个顶点最初都是孤立的，因此森林起始状态为 {A} {B} {C} {D} {E} {F}。
- A-C（1）。接受。属于不同碎片。森林变为
{AC} {B} {D} {E} {F}。累计 1。 - B-C（2）。接受。B 尚且孤立，C 与 A 在一起。森林变为
{ABC} {D} {E} {F}。累计 3。 - D-E（2）。接受。请注意，这里建起的碎片与第一个相距甚远。森林变为
{ABC} {DE} {F}。累计 5。 - E-F（3）。接受。森林变为
{ABC} {DEF}。累计 8。 - A-B（4）。拒绝。A 与 B 都已在
{ABC}中，因此这会闭合出环 A-C-B-A。丢弃。 - B-D（5）。接受。这条边在剩下的两个碎片之间架起桥梁。森林变为
{ABCDEF}。累计 13。
六个顶点接受了五条边，算法随即停止，根本没有去看 C-D（6）、C-E（7）与 D-F（8）。最终得到的树由 A-C（1）、B-C（2）、D-E（2）、E-F（3）、B-D（5）组成，总权重为 13，与 Prim 在同一个图上求得的树完全一致。
第 3 步是这个算法与众不同之处。此时 Prim 无法取用 D-E，因为它的两个端点都还没有接触到那棵正在生长的树。Kruskal 却毫不在意：它欣然在图的另一侧另起一个互不相干的碎片，把连接的事留到以后再说。而第 5 步则展示了环性质的实际作用：被拒绝的，恰好就是它将要形成的那个环上最重的边。
5. 并查集：让它跑得快的那个结构
判断两个顶点是否已经连通，最朴素的办法是从其中一个出发做一次遍历，看能否到达另一个。这样每条边要花 O(V)，会把整个算法拖到 O(V * E)，比它本该配合的排序还要糟糕。
并查集（不相交集合结构）能以近乎常数的时间回答这两个问题。它把每个碎片维护成一棵由父指针构成的树，树根处有一个代表元，并提供两个操作：
find(x)返回 x 所在碎片的代表元。两个顶点位于同一碎片，当且仅当它们的代表元相同。union(x, y)把一个根挂到另一个根之下，从而合并两个碎片。
两项优化让它快到可以从复杂度分析中消失。按秩合并总是把较矮的树挂到较高的树下，避免结构退化成一条链。路径压缩则在每次 find 过程中，把沿途访问到的每个节点直接改指向根，于是随着算法推进，重复查询会越来越便宜。
两者兼备时，对 n 个元素执行 m 次操作的代价为 O(m α(n))，其中 α 是反阿克曼函数。它增长得极其缓慢，对任何能装进可观测宇宙的输入都小于 5，因此 Kruskal 中并查集那部分工作，实际上是与边数成线性的。
6. 实现与伪代码
由于难点都由并查集承担，算法本身相当简短。
function Kruskal(V, edges):
将 edges 按权重升序排序
对每个顶点 v 执行 makeSet(v) // V 个单元素碎片
mst = []
for 按序取出每条边 (u, v, w):
if find(u) != find(v): // 分属不同碎片
union(u, v)
mst.append((u, v, w))
if size(mst) == V - 1: // 提前退出：树已完成
break
return mst有两处细节值得说明。break 对正确性并非必需，因为其后的每条边反正都会被拒绝；但在稠密图上，它能跳过列表的绝大部分。而完全去掉 break 也不是缺陷：正是这一点把它变成了求最小生成森林的算法，详见下文。
find(u) != find(v) 这个比较，是全篇唯一涉及环的地方。任何位置都没有显式的环检测，而这正是该思路的优雅之处：连通性的记账工作隐式地完成了它。
7. 时间与空间复杂度
- 排序：
O(E log E)。它主导了其余一切。由于E < V2，有log E < 2 log V，因此该界也等价地写作O(E log V)。 - 并查集：
O(E α(V))。每条边至多两次find与一次union。实际上是线性的。 - 总体：
O(E log E)。就是排序，别无其他。 - 空间：
O(V + E)。父数组与秩数组为O(V)，边列表本身为O(E)。
由于代价集中在一处，所有有价值的优化都针对排序。如果边本来就已排好序，或权重是可用基数排序、计数排序处理的小整数，整个算法就降到 O(E α(V))，非常接近线性。部分排序或惰性建堆同样有帮助：你很少需要完整的顺序，因为算法通常远在触及最重的那些边之前就已停止。
8. Kruskal 与 Prim
两者都是贪心算法，都由同一对定理提供依据，而且在边权互不相同的图上返回完全相同的树。实际差别源自各自在过程中保持连通的对象。
Kruskal Prim
结构 碎片构成的森林 一棵不断生长的树
驱动 排好序的边列表 优先队列
依赖 并查集 堆（或 V x V 扫描）
代价 O(E log E) O(E log V)，稠密 O(V^2)
擅长 稀疏图 稠密图
非连通 给出生成森林 只覆盖一个连通分量经验准则就是稠密程度。在稀疏图上 E 很小，排序开销低，Kruskal 胜出。在 E 接近 V2 的稠密图上，给约 V2 条边排序要花 O(V2 log V)，而配合邻接矩阵的 Prim 只需平直的 O(V2)，于是反超。
9. 实践要点与常见陷阱
生成森林与非连通图
这里 Kruskal 拥有一项真正的结构性优势。把它跑在非连通图上，它根本无法凑满 V - 1 条被接受的边。它会把边列表走完，而留下的正是一片最小生成森林：每个连通分量各自的最小生成树，一趟算完，无需任何特殊处理。
Prim 从单一起点做不到这一点。从某个顶点启动后，它覆盖该顶点所在的分量便停止，悄无声息地返回一棵看似合法、实则只覆盖了图之一部分的树。要补齐其余部分，就必须察觉这一缺口，并对每个分量各从一个未访问顶点重新启动一次。这个计数同时也是诊断依据：若 Kruskal 结束时接受了 V - 1 条边，说明图是连通的；若只接受了 V - k 条，说明图有 k 个连通分量。
最大生成树
把升序排序改成降序，算法的每一行依然成立。环性质会转化为在取相反数后的权重上的割性质论证，于是你得到的是最重的生成树。把权重取相反数、算法原样运行，效果同样良好。
逆向删除法
Kruskal 的镜像版本：把边从最重到最轻排序，逐条删除，除非删掉它会让图断开。它由同一条环性质反过来读所支撑，得到的树也相同。它很少被采用，因为每次删除后的连通性检测远比一次并查集查询昂贵。
权重相同
当多条边权重相同时，图可能拥有不止一棵最小生成树，你得到哪一棵取决于排序如何处理这些并列项。上面的例子中就有一处并列：B-C 与 D-E 权重都是 2。由此产生的各棵树同样最优，因此任何拿固定边列表去比对的测试都很脆弱。应当改为比较总权重。
自环与重边
自环必定通不过 find(u) != find(v) 这一判断，会被自动丢弃，无需特殊处理。在重边之中，最便宜的那条会先被走到并接受，其余的随后作为成环边被拒绝。Kruskal 对杂乱输入的容忍度异常之高。
10. 变体与实际应用
网络与基础设施规划
最初的动机：用尽可能少的电缆、管道或轨道，把一组固定站点连接起来。当输入本来就是一份带成本的候选连接清单时（这类数据通常正是如此呈现的），Kruskal 以边为中心的视角便格外契合。
层次聚类
运行 Kruskal 并记录碎片合并的先后顺序，你实际上就完成了一次单连接凝聚式聚类。这串合并序列正是树状图，而在 V - k 条边处提前停止，恰好留下 k 个簇。正是这种等价关系，解释了最小生成树为何在无监督学习中如此常见。
图像分割
把像素视为顶点、把灰度差异视为边权，Felzenszwalb 与 Huttenlocher 的分割算法本质上就是 Kruskal，只是把合并条件换成了“碎片内部差异与当前边权的比较”。
电路与版图设计
在固定焊盘之间最小化总走线长度，正是一个最小生成树问题，而候选走线构成的边列表，本就是布线器手头现成的数据。
11. 学术资源与历史
与被至少三次独立发现的 Prim 算法不同，这个算法的归属十分清晰。
- Joseph B. Kruskal（1956）在一篇仅三页的札记 On the shortest spanning subtree of a graph and the traveling salesman problem 中发表了它，刊于 Proceedings of the American Mathematical Society。该文比 Prim 的论文早一年，比 Borůvka 的晚三十年。
- Otakar Borůvka（1926）早在数十年前就提出并解决了最小生成树问题，起因是规划摩拉维亚乡村的电气化。
- Robert Tarjan（1975）证明了采用按秩合并与路径压缩的并查集具有近乎常数的均摊界，正是这一结果把 Kruskal 中非排序部分的代价钉在了
O(E α(V))。
关于该问题完整的归属考据，参见 Graham 与 Hell 的论文。若需要割性质、环性质以及两个算法的严谨证明，标准参考书是 Cormen、Leiserson、Rivest 与 Stein 合著的 Introduction to Algorithms 中关于最小生成树的一章。完整文献信息列于本文末尾。
常见问题
为什么 Kruskal 算法可以安全地拒绝一条边？
因为环性质：任意一个环上最重的那条边都可以不进入最小生成树。当 Kruskal 拒绝一条边时，它的两个端点已经处在同一个碎片中，这意味着它们之间早已存在一条路径，而该路径由更早被接受、因而不重于当前这条的边构成。于是被拒绝的边正是它将要闭合的那个环上最重的一条，丢弃它不会有任何损失。
Kruskal 算法为什么需要并查集？
算法必须对每条边判断其两个端点是否已经连通。用图遍历来回答这个问题，每条边要花 O(V)，会主导整个运行时间。并查集借助按秩合并与路径压缩，能以近乎常数的时间作答，使全部连通性判断的总代价为 O(E alpha(V))，其中 alpha 是反阿克曼函数，对任何实际输入都小于 5。
什么时候该用 Kruskal 而不是 Prim？
在稀疏图上、在输入本来就是边列表时、或者在图可能非连通时，优先选 Kruskal。它的代价由 O(E log E) 的排序主导，当 E 较小时非常便宜；而在非连通图上，它一趟就能自然地给出最小生成森林。在稠密图上则优先选 Prim，因为采用邻接矩阵的实现只需平直的 O(V^2)，并且避免了给大约 V 平方条边排序。