最小生成树相关名词
- 连通图：在无向图中，若任意两个顶点 vi 与 vj 都有路径相通，则称该无向图为连通图。
- 强连通图：在有向图中，若任意两个顶点 vi 与 vj 都有路径相通，则称该有向图为强连通图。
- 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接两个顶点的代价，称这种连通图叫做连通网。
- 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部 n 个顶点，但只有足以构成一棵树的 n-1 条边。一颗有 n 个顶点的生成树有且仅有 n-1 条边，如果生成树中再添加一条边，则必定成环。
- 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
最小生成树算法
Kruskal 算法
此算法可以称为”加边法”，初始最小生成树边数为 0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里（原文图片丢失，据文字重绘）：
flowchart TD
A["把图中的所有边按代价从小到大排序"] --> B["把图中的 n 个顶点看成独立的 n 棵树组成的森林"]
B --> C{"按权值从小到大选择边，<br/>所选边连接的两个顶点 ui、vi<br/>是否属于两棵不同的树？"}
C -- 是 --> D["该边成为最小生成树的一条边，<br/>并将这两棵树合并为一棵树"]
D --> E{"所有顶点都在一棵树内<br/>或已有 n-1 条边？"}
C -- 否 --> E
E -- 否 --> C
E -- 是 --> F["最小生成树构造完成"]具体步骤：
- 把图中的所有边按代价从小到大排序；
- 把图中的 n 个顶点看成独立的 n 棵树组成的森林；
- 按权值从小到大选择边，所选的边连接的两个顶点 ui、vi 应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树；
- 重复步骤 3，直到所有顶点都在一颗树内或者有 n-1 条边为止。
Prim 算法
此算法可以称为”加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点 s 开始，逐渐长大覆盖整个连通网的所有顶点：
- 图的所有顶点集合为 V；初始令集合 u = {s}，v = V − u；
- 在两个集合 u、v 能够组成的边中，选择一条代价最小的边 (u0, v0)，加入到最小生成树中，并把 v0 并入到集合 u 中；
- 重复上述步骤，直到最小生成树有 n-1 条边或者 n 个顶点为止。
由于不断向集合 u 中加点，所以最小代价边必须同步更新；需要建立一个辅助数组 closedge，用来维护集合 v 中每个顶点与集合 u 中最小代价边的信息。
总结
因为 Kruskal 涉及大量对边的操作，所以它适用于稀疏图；普通的 Prim 算法适用于稠密图，但堆优化的 Prim 算法更适用于稀疏图，因为其时间复杂度是由边的数量决定的。
参考文章
- https://blog.csdn.net/luoshixian099/article/details/51908175
- https://www.cnblogs.com/wuxiangnong/p/10885129.html
系列导航
- 上一篇：图：拓扑排序
- 下一篇：图：最短路径 Dijkstra & Floyd
- 相关篇：图：基础和 Overview