【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)

三、讨论

  • 最小生成树是否唯一?

    • 不一定
    • 试设计算法生成所有的最小生成树
  • 如果边的权都不相等

    • 一定是唯一的

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学