最近在学习 Kruskal 算法。这是一个简单的最小生成树算法，流程很简单，简单到让人怀疑——这样构造的树，怎么就恰好是一棵最小生成树呢？我在网上查找了相关资料，但似乎都省略了一些“显然”的证明，或者是有很多术语，导致我看得一头雾水，于是我想自己写一段完整、易懂的证明，也就是说它可能有些啰嗦，但是每一步的推进都是很好理解的。按照我的预想，本文仅需基本的初中数学知识以及对图论和集合论的一些基础概念的了解即可理解。之后我会抽空补上图示，因为有时候发现纯文字确实有些不直观。

前置知识

首先说明下会用到的定义或符号：

  • 空集合：\(\varnothing\)
  • 差集运算：若 \(A \setminus B = C\)，则有 \(B \cup C = A\) 且 \(B \cap C = \varnothing\)。简单理解便是 \(A\) “减去” \(B\)。
  • 边（Edge）：本文中的边均为带权无向边，无特殊说明用一个小写字母表示。
  • 边集（Edge Set）：无特殊说明用一个大写字母表示。
  • 边或边集的权值：\(W(e)\) 代表边 \(e\) 的权值；\(W(E)\) 代表边集 \(E\) 的权值，即 \(E\) 中所有边的权值和。

然后说明涉及到的概念：

流程

算法的流程非常简单，一句话就可以说清楚。

我们从任意两点间没有边连接的情况下，一步步加边，直到生成一棵树。按边权从小到大遍历每一条边，如果这条边加入后不会构成环路，则将其添加，否则舍弃，直到所有节点都被连通（即构成一棵树）。

或者更加形式化地说，我们将维护一个边集 \(E_i\)， \( E_i = \begin{cases} \varnothing & \text{if } i = 0 \\ E_{i-1} \cup \{e_i\} & \text{if } 1 \leq i < n \end{cases} \)

其中边 \(e_i\) 满足以下性质：

如此构造的 \(E_{n-1}\) 即为最小生成树，其中 \(n\) 为节点个数。

证明

本着“完整”的原则，我会将一些“显然”的证明放在脚注中。

我们使用一种同样简单但有效的方法——数学归纳法，来证明算法的正确性。我们只需证明，边集 \(E\) 在一步步加入边的过程中，始终是某个最小生成树的子集即可，即：

  1. 当 \(E = \varnothing\) 时，\(E\) 是某个最小生成树的子集。
  2. 当 \(E\) 是某个最小生成树的子集时，若在 \(E\) 中加入一条边 \(e\) 构成新的边集 \(E'\)，则 \(E'\) 也是某个最小生成树的子集。

不难发现命题2存在递推的性质，如果这两个命题成立，则我们可以向集合中重复地添加新的边，直到再也无法加入新的边，也就是加入任意一条边都会形成环的时候停止。这意味着此时的 \(E\) 已经构成一个生成树[^1]，并且由于它是某个最小生成树的子集，此时它便是最小生成树。

命题1显然是成立的[^2]，那么接下来我们将证明命题2。

外推命题的证明

在 \(E \subset T\) 的情况下，接下来加入一条不会构成环路的边 \(e\) 到 \(E\) 中构成新的 \(E'\)（即 \(E' \setminus E = \{e\}\)），现在我们需要证明 \(E'\) 仍然某个最小生成树的子集。

显然，如果 \(e \in T\)，那么 \(E' \subset T\)，此时命题成立。不过我们感兴趣的是，若 \(e \notin T\)，命题是否仍然能成立[^3]。

由于 \(T\) 是一棵树，任意两节点间有且仅有一条路径相连；此时再加入一个不属于 \(T\) 的边 \(e\)，必然会构成一个环 \(C \subset T \cup \{e\}\)[^4]，且存在一条边 \(f \in C\) 满足 \(f \notin E'\)，因为若无法找到这样的 \(f\)，意味着 \(C \subset E'\)，即 \(E'\) 中存在一个环，且一定由 \(e\) 的加入构成[^5]，这不符合算法时刻保持无环路的规则，因此 \(f\) 必然存在。\(W(f)\) 与 \(W(e)\) 比较，有且仅有三种情况：

假设 W(e) < W(f)

此时我们可以通过 \(e\) “绕路”，构造一棵生成树[^6] \(T' = T \setminus \{f\} \cup \{e\}\)，使得 \(W(T') = W(T) - W(f) + W(e) < W(T)\)，于是我们找到了一棵比 \(T\) 的权值和更小的生成树，这和 \(T\) 是最小生成树的前提矛盾，故假设错误。

假设 W(f) < W(e)

由于 \(f\) 不属于 \(E'\) ，那么按照算法规则，遍历顺序按边权从小到大，我们可以由此推断之前已经遍历到 \(f\)，并且将其舍弃。根据算法规则，这意味着当遍历到 \(f\) 时，如果加入 \(f\) 将在当时的 \(E\) （记作 \(E_i\)）中产生环。然而我们已知 \(f \in T\)，就是说加入 \(f\) 事实上并不会在 \(T\) 中构成环，那么就更不会在 \(E_i\) 中构成环了[^7]，因此产生矛盾，假设错误。

W(e) = W(f)

考虑 \(T' = T \setminus \{f\} \cup \{e\}\)。这同样是一棵生成树[^8]，并且 \(W(T') = W(T) - W(f) + W(e) = W(T)\)，故 \(T'\) 同样是一棵最小生成树，此时 \(E' \subset T'\)，命题成立。

结论

综上所述，加入边 \(e\) 的边集 \(E'\) 仍然是某个最小生成树的子集，命题2成立。由此我们便证明了 Kruskal 算法的正确性。

[^1]: 假设此时未形成生成树，且根据连通图的性质，我们至少能找到一对节点，它们之间没有直接的边相连，并且原图中有一条连通两节点的边。此时我们就可以将这条边加入而不形成环（这仍然要进一步证明），故不符合“无法再加入边”的前提，假设不成立，故此时一定形成生成树。

[^2]: 空集是任何集合的子集。

[^3]: 需要注意的是，\(T\) 是一个特定的最小生成树，但最小生成树不是唯一的。也就是说，\(e \notin T\) 并不意味着此时 \(E'\) 一定不被任何最小生成树包含。

[^4]: 对于 \(e\) 两端的节点来说，在未加入 \(e\) 时两节点在 \(T\) 上已经存在一条路径（且仅存在一条）使两者连通，故此时加入 \(e\) 后两者间便有两条不同的连通路径，于是形成了环路。

[^5]: 因为前提是 \(E \subset T\)，而 \(T\) 中不存在环路，故 \(E\) 中也无环路。而此时 \(E'\) 中却存在环路，说明一定是由 \(e\) 的加入导致的，也就是说该环路中一定包含 \(e\)。

[^6]: 已知 \(T\) 是一棵生成树，要证明 \(T'\) 是一棵生成树，只需要证明它连通所有点且不含环。对于前者，由于唯一被拿掉的边是 \(f\)，\(f \in C\)，故我们只需考虑 \(C\) 上的点是否仍然连通。我们知道一个完整的环去掉任何一条边，环上的点仍然保持连通；\(C \subset T \cup {e}\)，也就是 \(C \setminus {f} \subset T \cup {e} \setminus {f}\)，故 \(C\) 上所有点仍然保持连通。对于后者，我们知道一棵树加入一条边后形成的环是唯一的，因此加入 \(e\) 形成的环仅有可能是 \(C\)；而 \(C\) 上的一条边 \(f\) 已经在 \(T'\) 中被“拿掉”了，不可能形成环。

[^7]: 由于 \(E_i \subset E \subset T\)，如果在 \(E_i\) 中形成环，这个环一定属于 T，也就是说一定会在 T 中形成环。

[^8]: 参考脚注6。

参考

后记

这篇文章从开题到现在已经拖了两个多月了，然而现在也是匆匆忙忙发布，之后还会修改和补充内容，缺失的脚注 Markdown 渲染之后也会加上。

写这篇文章的过程中，我也常被各种逻辑绕晕。依我来看，要真正掌握某个算法，不仅要能对其进行详尽的证明，更重要的是在脑海中有一个直观的数学直觉，也就是说脱离细枝末节，全局地理解其合理性。写完这篇文章，对于这个算法的直观感受，其实我还是没有的。