【7.6】图的最小生成树
图 G 的生成树是一棵包含 G 的所有顶点的树，树上所 有权值总和表示代价，那么在 G 的所有的生成树中
代价最小的生成树称为图 G 的 最小生成树 (minimum-cost spanning tree，简称 MST)
一、Prim 算法
- 与 Dijkstra 算法类似——也是贪心法
- 从图中任意一个顶点开始 (例如 v0)，首先把这个顶点包括在 MST，U=(V*, E*) 里。 初始 V*= {v0} , E* = {}
- 然后在那些其一个端点已在 MST 里，另一个端点 还不是 MST里的边，找权最小的一条边 (vp, vq) ，并 把此vq 包括进 MST 里……
- 如此进行下去，每次往 MST 里加一个顶点和一条权最 小的边，直到把所有的顶点都包括进 MST 里
- 算法结束时V*=V,E*包含了G中的n-1条边
1.1 Prim 算法的 MST 性质
- 设 T(V*，E*) 是一棵正在 构造的生成树
- E 中有边 e= (vx，vy)， 其中vx∈v*，vy不属于V*
- e 的权 w(e) 是所有一个端 点在V* 里，另一端不在 V* 里的边的权中最小者
- 则一定存在 G 的一棵包 括 T 的 MST 包括边 e= ( vx，vy)
1.2 反证法证明 MST 性质
-
设G的任何一棵包括 T 的 MST 都不包括 e= ( vx，vy) ，且设 T’ 是一棵这样的 MST
-
由于 T’ 是连通的，因此有 从 vx 到 vy 的路径 vx，…，vy
-
把边 e= ( Vx，Vy) 加进树 T’，得到一 个回路 vx，…，vy，vx
-
上述路径 vx，…，vy 中必有边 e’= (vp ，vq)，其中vp∈V*，vq 不属于 V*，由 条件知边的权 w(e’)≥w(e)，从回路中去 掉边 e’
-
• 回路打开，成为另一棵生成树 T”，T” 包括边 e= (vx，vy)，且各边权的总和不 大于 T’ 各边权的总和
-
因此 T” 是一棵包括边 e 的 MST，与 假设矛盾，即证明了我们的结论
-
也证明了 Prim 算法构造 MST 的方 法是正确的。因为我们是从 T 包括任意一个顶点和0 条边开始，每一步加进去的都是 MST 中应包括的边，直至最后得到 MST
1.3 Prim 算法
在 Dist 数组中找最小值:
1.4 Prim 算法时间复杂度
- Prim 算法非常类似于 Dijkstra 算法
- Prim 算法框架与 Dijkstra 算法相同
- Prim 算法中的距离值不需要累积，直接用最小边
*本算法通过直接比较 D 数组元素，确定代价最小 的边就需要总时间O(n^2);取出权最小的顶点后 ，修改 D 数组共需要时间O(e)，因此共需要花费 O( n^2) 的时间
- 算法适合于稠密图
- 对于稀疏图，可以像 Dijkstra 算法那样用堆来保存距 离值
二、Kruskal 算法
-
首先将 G 中的 n 个顶点看成是独立的 n 个连通 分量，这时的状态是有 n 个顶点而无边的森林， 可以记为
$$ T = <V，\{ \}> $$ -
然后在 E 中选择代价最小的边，如果该边依附于 两个不同的连通分支，那么将这条边加入到 T 中 ，否则舍去这条边而选择下一条代价最小的边
-
依此类推，直到 T 中所有顶点都在同一个连通分 量中为止，此时就得到图 G 的一棵最小生成树
2.1 最小生成树 Kruskal 算法:
2.2 Kruskal 最小生成树算法
2.3 Kruskal 算法代价
- 使用了路径压缩，Different() 和 Union() 函 数几乎是常数
- 假设可能对几乎所有边都判断过了
- 则最坏情况下算法时间代价为 Θ (elog e)，即堆排序的时间
- 通常情况下只找了略多于 n 次，MST 就已经 生成
- 时间代价接近于 Θ (nlog e)
三、讨论
-
最小生成树是否唯一?
-
不一定
-
试设计算法生成所有的最小生成树
-
如果边的权都不相等
-
一定是唯一的
参考资料
北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾
