最小生成树（进阶）
复习
- 并查集：维护分组与连通性
- 优先队列：每次取出最小的元素
- 图：带权无向图
TL;DR
- 最小生成树用最低的总代价连接所有节点
- Kruskal：按边权从小到大加边，用并查集避免成环
- Prim：从一点出发，每次加入最近的节点
- 两种方法都借助了前面学过的工具
正文
设想要为一个地区的若干城市铺设通信线路，每对城市之间铺线的成本不同。怎样用最低的总成本把所有城市连起来，又不会多铺不必要的线？
这就是最小生成树（MST，Minimum Spanning Tree）问题。
什么是生成树
先理清两个概念：
- 生成树：能用最少的边把所有节点连通，且不含环的树。n 个节点，只需 n-1 条边
- 最小生成树：在所有生成树里，总边权最小的那一棵
“连通所有节点”保证没有城市掉队，“不含环”保证不多花冤枉钱——因为成环就意味着有一条边是多余的。
Kruskal：从小边开始加
Kruskal 算法的思路非常直白：
- 把所有边按权重从小到大排序
- 依次考虑每条边：如果它的两个端点还不连通，就把这条边加进来
- 如果加入它会成环，就跳过
这里的“判断两点是否已经连通”“加边后会不会成环”，正是并查集的任务：加入一条边前，先查两端是否同组；不同组才加，并把它俩合并。
从小边开始贪心地加，配合并查集防环，就能得到最小生成树。
Prim：从一点长出去
Prim 算法换了个角度：从一个起点出发，每次从“连接已选节点与未选节点的边”里，挑一条最小的，把新节点拉进来。不断长大，直到覆盖所有节点。
“每次挑最小的边”这件事，恰好由优先队列来完成。
两种思路，两份工具
把两者对比一下：
- Kruskal：以边为中心，用并查集防环
- Prim：以点为中心，用优先队列取最小边
它们殊途同归，都能求出最小生成树，只是从不同角度切入。更重要的是，它们把前面学过的好几个工具——排序、并查集、优先队列——组合在了一起。
复杂算法往往不是发明新东西，而是把已有的零件巧妙地拼起来。 这正是整部教程一直在演示的事情。
思考题 1
Kruskal 算法为什么用并查集来避免成环？
思考题 2
Kruskal 和 Prim 分别借助了前面学过的哪个结构？
小结
知识点
- 生成树以最少边连通所有节点且无环
- 最小生成树的总边权最小
- Kruskal 按边权排序加边，用并查集防环
- Prim 从一点扩展，用优先队列取最小边
参考资料
- Wikipedia(zh)：最小生成树：总权最小的生成树
- Wikipedia(zh)：克鲁斯卡尔算法：按边权逐步加入的 MST 算法
思考题答案（仅供参考）
思考题 1
因为 Kruskal 需要反复判断“加入某条边后两端是否已经连通、会不会成环”。并查集恰好擅长维护分组与连通性：查两端是否同组即可判断，不同组才加入并合并，从而高效地避免成环。
思考题 2
Kruskal 借助了排序（按边权排边）和并查集（判断连通、防环）；Prim 借助了优先队列（每次取出连接已选与未选节点的最小边）。两者都把前面的工具组合了起来。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪