前置知识和定义#

在开始学习最小生成树之前，先了解一些前置知识。

子图#

对于一张图 $G=(V,E)$ ，如果存在一张图 $H=(V',E')$ 满足 $V'\subseteq V$ 且 $E'\subseteq E$ ，则称 $H$ 是 $G$ 的一个子图。记作 $H\subseteq G$ 。

如果存在 $H \subseteq G$ 满足 $V'=V$ ，则称 $H$ 是 $G$ 的一个生成子图。

生成子图又称为支撑子图。

生成树：一个无向连通图的生成子图,且同时要求是树。也即在图的边集选择了 $n-1$ 条边，将图中的所有顶点连接起来。

我们定义，一个无向连通图的 最小生成树，是指这个图中边权和最小的生成树。

Kruskal 算法是一种常见简单的用于求最小生成树的算法。此算法的基本思想就是贪心的从小到大加入边。

显然，我们需要使用并查集来维护每个点所在的连通块。那么，此算法的时间复杂度就为 $O(m\log m)$ ，其中 $m$ 是边数。

我们使用数学归纳法证明 Kruskal 算法的正确性。

基础：算法开始前，显然成立。

归纳：假设算法在加入了 $k-1$ 条边后，生成了一个最小生成树 $T$ 。我们需要证明，加入第 $k$ 条边 $(u,v)$ 后，生成的最小生成树 $T'$ 也成立。

我们可以分两种情况讨论：

如果 $(u,v)$ 不在 $T$ 中，那么 $T'$ 就是 $T$ 加上 $(u,v)$ 这条边。显然， $T'$ 是一个最小生成树。
如果 $(u,v)$ 在 $T$ 中，那么 $T'$ 就是 $T$ 去掉 $(u,v)$ 这条边，加上 $(u,v)$ 这条边的最小生成树。根据归纳假设， $T$ 是一个最小生成树，所以 $T'$ 也是一个最小生成树。

我们使用反证法证明 Kruskal 算法的正确性。

假设 Kruskal 算法得到的生成树 $T$ 不是最小生成树，那么必然存在某个最小生成树 $T_{opt}$ ，使得 $w(T_{opt}) < w(T)$ ，其中 $w(\cdot)$ 表示生成树的边权和。

设 $e_k = (u,v)$ 是 Kruskal 算法选择的第一个不在 $T_{opt}$ 中的边（按边权从小到大排序后的第 $k$ 条边）。由于 Kruskal 算法会选择这条边，说明在加入 $e_k$ 之前， $u$ 和 $v$ 不在同一个连通块中。

现在考虑 $T_{opt} \cup \{e_k\}$ ，这个图必然包含一个环（因为 $T_{opt}$ 是生成树，加入任何边都会形成环）。这个环中至少包含一条边 $e'$ 满足 $w(e') \geq w(e_k)$ （因为 $e_k$ 是连接这两个连通块的最小权边）。

我们可以构造一个新的生成树 $T' = T_{opt} \cup \{e_k\} \setminus \{e'\}$ 。显然：

但是这与 $T_{opt}$ 是最小生成树的假设矛盾，因为我们找到了一个权值不大于 $T_{opt}$ 的生成树 $T'$ ，且 $T'$ 包含了 $e_k$ 。

通过重复这个过程，我们可以证明 Kruskal 算法得到的生成树 $T$ 必须是最小生成树，从而证明了算法的正确性。