最小生成树从入门到精通

1 什么是最小生成树

生成树是包含原图所有点的连通无环子图。最小生成树是这些树中边权和最小的那个。

2 完全图上生成树的个数

如果一个图上的生成树的数量并不是很多的话，那或许暴力枚举也可以是一个求解最小生成树的好方法。然而现实是残酷的。我们首先给图上的点进行一个标号，假设图上有 n 个点，那么标号就是 1 - n 。接下来我们分别给出从图上的一个生成树到一个序列的映射，以及一个从序列到生成树的映射。这样一个双射就可以说明生成树的数量和序列的数量一样。
对于一个生成树，我们用这样的方法生成一个序列：

• 如果这个树只剩下两个节点，则停止流程。否则每次找到一个树上的最小标号的叶子，把它从树上去掉，同时输出它所连接的点的标号。因为是一个叶子，所以它只连接一个点。

那么很显然，这样的生成方式保证每个生成树只对应一个序列。
有了上述流程，想要找到它的逆流程其实也是简单的。对于一个序列 A，我们这样还原一个生成树：

• 首先不在序列里的点显然就是叶子们。我们同时维护一个叶子序列和非叶子序列（叶子序列按照大小顺序，非叶子序列按照原始顺序）。一开始的时候非叶子序列就是原始序列 A，叶子序列就是不在 A 里的剩下的点。我们每次从非叶子序列的开头拿出一个数，并且把它对应的点连接到叶子序列里的第一个数对应的点上。这里拿出的意思是这个数字就被删除掉了。
• 额外需要考虑的是非叶子也可以转化为叶子。当一个数不再出现在非叶子序列中时，它就应该被插入到叶子序列里。

说起来还是比较麻烦，我们来看一个例子。假设序列是 6 6 2 1 1 3 3 ，我们来看看它对应的树是什么样的。首先我们知道这个序列长度是 7 ，所以可以知道这个图一共有 9 个点（因为生成序列的时候剩下两个节点就停止流程了）。
第一步：
第二步：
这一步中需要注意到我们把第二个 6 拿出来的时候非叶子序列里就没有 6 了，这个时候要把 6 加入到叶子序列里（叶子序列是从小到大排列的）。这样做的原因是我们从树生成序列的时候，4 和 5 这两个叶子被删除之后 6 就变成叶子了。
第三步：
下来的步骤不赘述，我们放上最终的图：
这样我们知道了生成树的个数是非常多的，因为这样的序列可以有 个。这个序列叫做 Prufer 序列。

3 最小生成树的算法

3.1 Kruskal 算法

这个算法相信大家也是耳熟能详了。我们把边按照权值从小到大排序之后依次加入一个空图之中。每次都加边，除非这条边是冗余的（redundant）。冗余指的是这条边连接的两个点已经是在同一个连通块了。检查是否在连通块里可以使用并查集，最终复杂度为：，其中 e 是边数，n 是点数。
这个算法的正确性可以这样证明：假设算法生成的 Tk 不是最小生成树，那么我们假设最小生成树是 To。To 必然有一条不在 Tk 里的边，我们把这个边 e 并到 Tk 里肯定会出现一个环。我们根据算法流程知道，这个环上的其他边一定权值小于 e ，不然当初就会先把 e 加到图里了。我们还知道这个环上有除了 e 之外的边不在 To 里，因为如若不然 To 就包含一个圈了。为什么是除掉 e 之外呢？因为 e 就是从 To 里挑出来的。

3.2 Prim 算法

这个算法的思路就是围绕着一个连通块不停的拓展边。每次从连通块延伸出去的边中挑一条权重最低的那条边，并把它加入到当前的连通块中。这个流程有一点像 Dijkstra 。
如果使用数组来模拟这个过程，复杂度是：。
显然可以用普通的堆来加速，复杂度是：。
所以我们可以根据图的稀疏程度来选择到底用哪个算法，最终可以得到一个复杂度的做法。（不是非常严谨）
这里我们注意到使用普通的堆加速不是非常好，因为我们想要的 decrese-key 操作普通堆其实是不支持的。我们只能往堆里加一个新的点。所以我们可以使用斐波那契堆来支持这个操作。斐波那契堆在稠密图上效果非常好，可以做到真正的复杂度。

3.3 Sollin’s 算法

这个算法基于这样一个观察：我们每个点连接的边里权值最小的那一条一定在最小生成树里。这一点可以通过 Krustal 算法的流程观察到，如果这条边都不在生成树里，当时是如何把那个点加到生成树里的呢？
根据这个观察我们可以得到这样一个做法：每次挑选出每个点连接的边里边权最小的，然后根据挑出来的这些边去缩点，也就是把连通块缩成一个点。然后缩点之后的图继续这样的操作。
那么显然每次缩点至少会少掉一半的点，所以复杂度。

3.4 Yao’s 算法

姚期智先生的一个做法，非常聪明。他的做法基于：确定时间线性时间找中位数算法。关于这个算法的介绍可以看参考[2] 那篇博文。这个找中位数的算法不同于我们常见的算法的地方在于它是真的确定性的线性时间，而且也非常简单，不过实际效果不是很好，但是具有很高的理论价值。
现在假设我们已经知道了如何在线性时间找到中位数。我们还是考虑 Sollin’s 的思路，不过这一次我们更加聪明一点。之前每次我们挑选出每个点连接的边里边权最小的方法就是遍历每一条边。但是我们知道这并不是非常的合理，因为有些边你在第一轮就发现它权值很大，其实很后面才需要去考虑，在之前其实是不需要再遍历它的。所以我们考虑把每个点邻接的边进行一个分组，组内无大小关系，但是保证第组的所有边一定比组的边的权值要小。每次挑选的时候先挑选第一组边，第一组挑完了才考虑第二组，以此类推，那么就不需要考虑所有的边，只需要考虑某个组内的边了。
现在假设已经分成了组，复杂度就变成了。我们考虑分组的复杂度：因为我们可以线性时间找到中位数，那么我们就可以线性时间把边的集合按照权值分成大小两半（一半比中位数，一半比中位数小）。那么分成组其实只需要的时间。简单的求导就可以知道的时候总体复杂度是最好的，所以最终复杂度为：。

3.5 Cheriton-Tarjan 算法

我们还是考虑改进 Sollin 算法，每次挑选边的时候我们不用简单的遍历，而是每个点都维护一个优先队列（这个必须要求是能快速合并的堆）。这样每次挑边出来就可以直接从优先队列中选择，而不是傻乎乎的一个一个遍历。

4 有趣的性质

首先有两个著名的性质：割最优性、环最优性。它们的含义分别是：

• 割最优性：从生成树上把某条边删去，形成了两个连通分量。如果这个树是最小生成树，那么删掉的这条边是整个图里连接这两个连通分量的边中权值最小的那个。
• 环最优性：往生成树上加入一条图里的边，一定会生成一个环。如果这个树是最小生成树，那么加入的这条边是生成的环里权值最大的那一条边。

这两个性质看起来非常显然，但是要证明它们和最小生成树之间的充要关系并不非常简单，具体可见：Simple and Naive Survey on MST
这两个性质是我们证明各种其他性质以及算法正确性的基石。
同时它还有一些有趣的性质，证明留作思考题：

1. 给定一个图和它的最小生成树。现在向图中加入一个新点和它连出去的边，可以根据已有的生成树时间构造新的生成树。（提示：可以先证明这样一个性质：新的图一定存在一个生成树，它只包含新加入的边和原生成树里的边）
2. 给定一个图和它的最小生成树。现在从图里删掉一个点，那么新的图中一定存在一个生成树，它包含所有原最小生成树中的边，除了那些被删掉的。
3. 给图中所有边的权值都加一个常数，不会改变图的最小生成树。
4. 一个图可以有很多个最小生成树，但是所有的最小生成树都有相同的边权集合。例如一个最小生成树包含条边，权值分别为，那么这个图的其他最小生成树的边的权值一定也是。
5. 改变图中任意一条边的权值，我们都能在时间基于原最小生成树重新生成一个最小生成树。考虑分类讨论：如果增大非最小生成树边，则不变；如果减小最小生成树边，则不变；如果增大最小生成树边，则利用割最优性原理找到更小的连接连通块的边，用找到的边替换被修改的边；如果减小非最小生成树边，则利用环最优性原理找到环上权值最大的边并把它替换掉。

Ref:
[1] Kruskal correctness: http://people.qc.cuny.edu/faculty/christopher.hanusa/courses/634sp12/Documents/KruskalProof.pdf
[2] Linear Time Median Finding: https://rcoh.me/posts/linear-time-median-finding/
[3] Slides about MST and cut optimality and path optimality conditions https://copland.udel.edu/~amotong/teaching/algorithm%20design/lectures/(Lec%2012)%20Greedy%20Strategy%20-%20Minimum%20Spanning%20Tree%20-%20Optimality%20Condition.pdf%20Greedy%20Strategy%20-%20Minimum%20Spanning%20Tree%20-%20Optimality%20Condition.pdf)