最小生成树

2022年11月6日 25点热度 0人点赞 0条评论

最小生成树的应用

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

概念

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

定义

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

  • 生成子图
  • 生成树

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

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

file

Kruskal 算法

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

前置知识

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

实现

图示:

file

伪代码:

file

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

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

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

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

证明

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

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

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

归纳:

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

file

Prim 算法

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

实现

图示:

file

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

其实跟 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)$.

伪代码:

file

注意: 上述代码只是求出了最小生成树的权值, 如果要输出方案还需要记录每个点的 $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$.

file

Boruvka 算法

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

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

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

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

  1. 计算每个点分别属于哪个连通块. 将每个连通块都设为没有最小边.
  2. 遍历每条边 $(u, v)$, 如果 $u$ 和 $v$ 不在同一个连通块, 就用这条边的边权分别更新 $u$ 和 $v$ 所在连通块的最小边.
  3. 如果所有连通块都没有最小边, 退出程序, 此时的 $E'$ 就是原图最小生成森林的边集. 否则, 将每个有最小边的连通块的最小边加入 $E'$, 返回第一步.

下面通过一张动态图来举一个例子 (图源自 维基百科):

file

当原图连通时, 每次迭代连通块数量至少减半, 算法只会迭代不超过 $O(\log V)$ 次, 而原图不连通时相当于多个子问题, 因此算法复杂度是 $O(E\log V)$ 的. 给出算法的伪代码:(修改自 维基百科)

file

习题

file

最小生成树的唯一性

考虑最小生成树的唯一性. 如果一条边 不在最小生成树的边集中, 并且可以替换与其 权值相同, 并且在最小生成树边集 的另一条边. 那么, 这个最小生成树就是不唯一的.

对于 Kruskal 算法, 只要计算为当前权值的边可以放几条, 实际放了几条, 如果这两个值不一样, 那么就说明这几条边与之前的边产生了一个环 (这个环中至少有两条当前权值的边, 否则根据并查集, 这条边是不能放的), 即最小生成树不唯一.

寻找权值与当前边相同的边, 我们只需要记录头尾指针, 用单调队列即可在 $O(\alpha(m))$($m$ 为边数) 的时间复杂度里优秀解决这个问题 (基本与原算法时间相同).

例题:POJ 1679

file

以下内容待续.

次小生成树

非严格次小生成树

定义

求解方法

严格次小生成树

定义

求解方法

代码

瓶颈生成树

定义

性质

例题

最小瓶颈路

定义

性质

应用

Kruskal 重构树

定义

性质

file

file

rainbow

没什么大用的码农; 贴图怪; bug制造者; 只会电脑开关机的开发;

文章评论