最小生成树

最小生成树的应用

最小生成树的应用场景很多, 小到我们要来个欧洲十国游, 怎么规划路径让交通费用最低, 大到国家的电力网, 公路网, 通信网, 怎么规划路径可以让建设成本最低, 学习了最小生成树后, 你就可以通过算法来计算出最佳路径了, 不仅如此, 所有涉及连接网络中所有节点的最优路径问题, 都可以通过最小生成树来处理.

概念

连通图: 在无向图中, 若任意两个顶点 $u$ 与 $v$ 都有路径相通, 则称该无向图为连通图.
强连通图: 在有向图中, 若任意两个顶点 $u$ 与 $v$ 都有路径相通, 则称该有向图为强连通图.
连通网: 在连通图中, 若图的边具有一定的意义, 每一条边都对应着一个数, 称为权; 权代表着连接连个顶点的代价, 称这种连通图叫做连通网.
生成树: 一个连通图的生成树是指一个连通子图, 它含有图中全部 $n$ 个顶点, 但只有足以构成一棵树的 $n-1$ 条边. 一颗有 $n$ 个顶点的生成树有且仅有 $n-1$ 条边, 如果生成树中再添加一条边, 则必定成环.
最小生成树: 在连通网的所有生成树中, 所有边的代价和最小的生成树, 称为最小生成树.

定义

在阅读下列内容之前, 请务必阅读图论相关概念与树基础部分, 并了解以下定义:

生成子图
生成树

我们定义无向连通图的 最小生成树(Minimum Spanning Tree, MST) 为边权和最小的生成树.

注意: 只有连通图才有生成树, 而对于非连通图, 只存在生成森林.

Kruskal 算法

Kruskal 算法是一种常见并且好写的最小生成树算法, 由 Kruskal 发明. 该算法的基本思想是从小到大加入边, 是个贪心算法.

前置知识

并查集,贪心,图的存储.

实现

图示:

伪代码:

算法虽简单, 但需要相应的数据结构来支持. 具体来说, 维护一个森林, 查询两个结点是否在同一棵树中, 连接两棵树.

抽象一点地说, 维护一堆集合, 查询两个元素是否属于同一集合, 合并两个集合.

其中, 查询两点是否连通和连接两点可以使用并查集维护.

如果使用 $O(m\log m)$ 的排序算法, 并且使用 $O(m\alpha (m, n))$ 或 $O(m\log n)$ 的并查集, 就可以得到时间复杂度为 $O(m\log m)$ 的 Kruskal 算法.

证明

思路很简单, 为了造出一棵最小生成树, 我们从最小边权的边开始, 按边权从小到大依次加入,如果某次加边产生了环, 就扔掉这条边, 直到加入了 $n-1$ 条边, 即形成了一棵树.

证明: 使用归纳法, 证明任何时候 K 算法选择的边集都被某棵 MST 所包含.

基础: 对于算法刚开始时, 显然成立 (最小生成树存在).

归纳:

假设某时刻成立, 当前边集为 $F$ , 令 $T$ 为这棵 MST, 考虑下一条加入的边 $e$.
如果 $e$ 属于 $T$ , 那么成立.
否则, $T+e$ 一定存在一个环, 考虑这个环上不属于 $F$ 的另一条边 $f$(一定只有一条).
首先,$f$ 的权值一定不会比 $e$ 小, 不然 $f$ 会在 $e$ 之前被选取.
然后,$f$ 的权值一定不会比 $e$ 大, 不然 $T+e-f$ 就是一棵比 $T$ 还优的生成树了.
所以,$T+e-f$ 包含了 $F$, 并且也是一棵最小生成树, 归纳成立.

Prim 算法

Prim 算法是另一种常见并且好写的最小生成树算法. 该算法的基本思想是从一个结点开始, 不断加点 (而不是 Kruskal 算法的加边).

实现

图示:

具体来说, 每次要选择距离最小的一个结点, 以及用新的边更新其他结点的距离.

其实跟 Dijkstra 算法一样, 每次找到距离最小的一个点, 可以暴力找也可以用堆维护.

堆优化的方式类似 Dijkstra 的堆优化, 但如果使用二叉堆等不支持 decrease-key 的堆, 复杂度就不优于 Kruskal, 常数也比 Kruskal 大. 所以,一般情况下都使用 Kruskal 算法, 在稠密图尤其是完全图上, 暴力 Prim 的复杂度比 Kruskal 优, 但 不一定 实际跑得更快.

两种算法区别从策略上来说, Prim 算法是直接查找, 多次寻找邻边的权重最小值, 而 Kruskal 是需要先对权重排序后查找的所以说, Kruskal 在算法效率上是比 Prim 快的, 因为 Kruskal 只需一次对权重的排序就能找到最小生成树, 而 Prim 算法需要多次对邻边排序才能找到

暴力:$O(n^2 + m)$.

二叉堆:$O((n+m)\log n)$.

Fib 堆:$O(n\log n + m)$.

伪代码:

注意: 上述代码只是求出了最小生成树的权值, 如果要输出方案还需要记录每个点的 $dis$ 代表的是哪条边.

证明

从任意一个结点开始, 将结点分成两类:已加入的,未加入的.

每次从未加入的结点中, 找一个与已加入的结点之间边权最小值最小的结点.

然后将这个结点加入, 并连上那条边权最小的边.

重复 $n-1$ 次即可.

证明: 还是说明在每一步, 都存在一棵最小生成树包含已选边集.

基础: 只有一个结点的时候, 显然成立.

归纳: 如果某一步成立, 当前边集为 $F$, 属于 $T$ 这棵 MST, 接下来要加入边 $e$.

如果 $e$ 属于 $T$, 那么成立.

否则考虑 $T+e$ 中环上另一条可以加入当前边集的边 $f$.

首先,$f$ 的权值一定不小于 $e$ 的权值, 否则就会选择 $f$ 而不是 $e$ 了.

然后,$f$ 的权值一定不大于 $e$ 的权值, 否则 $T+e-f$ 就是一棵更小的生成树了.

因此,$e$ 和 $f$ 的权值相等,$T+e-f$ 也是一棵最小生成树, 且包含了 $F$.

Boruvka 算法

接下来介绍另一种求解最小生成树的算法——Boruvka 算法. 该算法的思想是前两种算法的结合. 它可以用于求解 边权互不相同 的无向图的最小生成森林.(无向连通图就是最小生成树.)

为了描述该算法, 我们需要引入一些定义:

定义 $E'$ 为我们当前找到的最小生成森林的边. 在算法执行过程中, 我们逐步向 $E'$ 加边, 定义 连通块 表示一个点集 $V' \in V$, 且这个点集中的任意两个点 $u$,$v$ 在 $E'$ 中的边构成的子图上是连通的 (互相可达).
定义一个连通块的 最小边 为它连向其它连通块的边中权值最小的那一条.

初始时,$E' = \empty$, 每个点各自是一个连通块: