Kruskal算法计算器

伪代码

把所有边按权重排序，然后依次扫过这个列表，凡是连接两个不同连通分量的边就加入。并查集让「是否属于不同分量」这一判断几乎不花代价，这是整个算法高效的关键。

Kruskal(图):
    把所有边按权重升序排序
    对每个结点 v 执行 建立集合(v)
    mst = []

    按排序顺序对每条边 (u, v, w):
        若 查找(u) != 查找(v):    // 属于不同分量
            合并(u, v)
            mst.追加((u, v, w))
            若 mst 已有 V - 1 条边: 退出

    返回 mst

Kruskal 生长的是森林而非树。若干互不相连的片段各自独立发展，并在便宜的边把它们连起来时逐步合并，这正是它与 Prim 的结构性差异，也是 Kruskal 能免费处理非连通图的原因：它直接返回一片最小生成森林。其正确性同样来自把割性质应用到各分量的边界上，与 Prim 完全一致。

分步示例演算

在与 Prim 示例完全相同的图上构造最小生成树，以便在同一组数据上比较两者的发现顺序。

示例图: 无向边 A-B (2)、A-C (3)、B-C (1)、C-D (4) 和 B-D (7)。

1. 把边排序. 按权重排列：B-C 为 1、A-B 为 2、A-C 为 3、C-D 为 4、B-D 为 7。每个结点最初各自成为一个单元素集合。
2. 接受 B-C (1). B 与 C 属于不同集合，因此这条边被接受，两者合并。此时的分量为 {B, C}、{A} 和 {D}。
3. 接受 A-B (2). A 与 B 仍属于不同集合，因此接受并合并。此时的分量为 {A, B, C} 和 {D}。
4. 拒绝 A-C (3). A 与 C 现在已在同一集合中，这条边会形成环，因此被跳过。这正是与 Prim 可见的差别所在：一旦两个端点都进入树中，Prim 根本不会让 A-C 作为候选浮现出来。
5. 接受 C-D (4). C 与 D 属于不同集合，因此接受并合并。四个结点此时已归为一个分量，树也已有三条边，算法可以在完全不考察权重 7 的 B-D 的情况下停止。

最小生成树由 B-C、A-B 和 C-D 构成，总权重为 1 + 2 + 4 = 7，与 Prim 从 A 出发得到的结果完全一致。在边权互不相同的情况下两棵树必然相同，但发现顺序不同：Prim 依次取 A-B、B-C、C-D，从 A 向外生长；Kruskal 则按纯粹的权重顺序取 B-C、A-B、C-D，并在途中显式拒绝了一条会成环的边。这种顺序上的差别在可视化工具中一目了然，也是理解两个算法真正区别的最佳途径。

复杂度及其来源

时间: O(E log E) · 空间: O(V + E)

对边排序的代价 O(E log E) 支配了其余一切，而由于 E 至多为 V 的平方，log E 与 log V 只差常数因子，因此它等同于 O(E log V)。排序之后，循环至多执行 2E 次查找和 V - 1 次合并。在同时采用路径压缩与按秩合并时，每次操作的代价是 V 的反阿克曼函数，对任何能装入内存的输入都小于 5，可以按常数看待。因此并查集部分实际上是 O(E)，排序构成了全部开销。当边本身已经有序，或因权重是较小整数而可以用桶排序时，Kruskal 会降到接近线性，并明显优于 Prim。

何时使用克鲁斯卡尔最小生成树算法，何时不宜

Kruskal 与 Prim 解决的是同一个问题。稠密程度、边的顺序以及连通性决定了哪一个更合适。

常见陷阱

• 使用并查集却不做路径压缩或按秩合并. 朴素实现会退化成链表，每次查找变成 O(V)，把整个循环推到 O(E·V)。这两项优化各自只有几行代码，却正是那条「接近常数」的界限得以成立的原因。
• 比较结点本身而不是集合代表元. 判环的条件是 查找(u) != 查找(v)，而不是 u != v。直接比较结点会接受所有边，产生的是一个布满环的图而非一棵树，这个错误在极小的测试数据上很容易被忽略。
• 忘记在 V - 1 条边处停止. 这不是正确性缺陷，而是无谓的开销：树一旦有了 V - 1 条边就已完成，剩下的每条边都会被拒绝。在稠密图上这意味着大量被浪费的扫描。
• 在权重并列时以为答案唯一. 当多条边权重相同时，排序顺序决定了哪些边被选中，不同实现会产生总权重相同但边集不同的树。请比较总权重，而不是边的集合。
• 把它用于有向图. 与 Prim 一样，Kruskal 是为无向图定义的。有向情形的对应物是最小生成树形图，需要 Chu-Liu/Edmonds 算法。

常见问题

Kruskal 算法是怎样工作的？

它把所有边按权重排序，然后扫过这个有序列表：只要一条边的两个端点分属不同分量就加入，若两者已经连通则跳过。并查集以接近常数的时间回答连通性问题。接受 V - 1 条边之后，得到的就是一棵最小生成树。

Kruskal 算法的时间复杂度是多少？

O(E log E)，完全由边排序主导。并查集操作只增加 O(E·α(V))，其中 α 是反阿克曼函数，实际上等同于常数。若边已经有序或可用桶排序，整个算法会接近线性。

Kruskal 算法与 Prim 算法有什么区别？

Kruskal 从全局出发按权重顺序考察边，用并查集拒绝成环的边，生长出一片最终合并为一棵树的森林。Prim 则用优先队列从一个起始结点向外生长单棵连通的树。Kruskal 适合稀疏图或已排序的边，并且天然支持非连通输入；Prim 适合稠密图。

Kruskal 为什么需要并查集？

因为它对每条边只问一个问题：两个端点是否已经连通，而这个问题要问 E 次。并查集在路径压缩与按秩合并下能以接近常数的时间作答。若改为对每条边都跑一次遍历来重新计算连通性，代价将变成 O(E·V)。

Kruskal 能处理非连通图吗？

能，而且无需任何改动。它会直接返回一片最小生成森林，每个连通分量对应一棵树，因为它在运行过程中从不要求已接受的边构成单一的连通结构。相比之下，Prim 一旦耗尽包含其起点的那个分量就会停止。