5.5 最小(代价)生成树★3◎4

5.5 最小(代价)生成树★3◎4


5.5 最小(代价)生成树★3◎4
  如果连通图G的一个子图是一棵包含图G的所有顶点的树,则该子图称为G的“生成树&rdq…

5.5 最小(代价)生成树★3◎4

5.5 最小(代价)生成树★3◎4

  如果连通图G的一个子图是一棵包含图G的所有顶点的树,则该子图称为G“生成树”。生成树是连通图中包含图中的所有顶点的极小连通子图,并且图的生成树并不唯一,从不同的顶点出发进行遍历,可以得到不同的生成树。
  在连通网中,构造一个生成树,如果树中所有边代表的权值之和最小,那么就称这个生成树是“最小生成树”“最小代价生成树”。生成树的代价是指树上所有边的权值之和。
  最小生成树(Minimum Spanning Tree)简称MST,它有许多重要的应用。比如在n个城市之间建立通信网络,则连通n个城市只需要n-1条线路,那么如何选择这n-1条线路,使得总通信代价最小。
  最小生成树具有一个特别重要的性质:设N=(V,E)是一个连通网络,U是顶点集V的一个真子集。若(u,v)是G中具有性质“一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里”的边中,权值最小的一条,则一定存在N的一棵最小生成树包括边(u,v)。
  普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法正是通过这个性质来产生最小生成树的。
  1.普里姆算法
  (1)算法思想
  设连通网N=(V,{E})中,T=(U,TE)是存放MST的集合,其中TE是N的最小生成树的边的集合,U是N的最小生成树顶点的集合,V-U是图N中除去U中顶点的顶点集合。
  ①算法开始时,TE为空,U中存在一个初始顶点。
  ②考查图中满足以下条件的边:边的一端在U集合中的顶点中,另一端在V-U集合的顶点中,在这些边中寻找权值最小的一条,假设为(Vi,Vj),其中,Vi∈U,Vj∈V-U,那么将顶点Vj加入集合U中,将边(Vi,Vj)加入集合TE中。
  ③重复执行步骤共②n-1次,T即为所求。
  (2)算法实例
  用普里姆算法求图5-10(a)的最小生成树。
  初始时TE为空,从顶点V1开始生成,故U中存在一个顶点V1,其余步骤如表5-5所示。

表5-5 普里姆算法求最小生成树步骤

 

U

TE

U-V

U到U-V边及其权值

说    明

第1步操作 V1 V2、V3、V4 (V1,V2) 5
(V1,V3) 1
(V1,V4) 6
权值最小的边为(V1,V3),所以顶点V3进入集合U,边(V1,V3)进入集合TE
第1步结果 V1、V3 (V1,V3) V2、V4   如图5-10(b)所示
第2步操作 V1、V3 (V1,V3) V2、V4 (V1,V2) 5
(V1,V4) 6
(V3,V2) 3
(V3,V4) 9
权值最小的边为(V3,V2),所以顶点V2进入集合U,边(V3,V2)进入集合TE
第2步结果 V1、V2、V3 (V1,V3)
(V3,V2)
V4   如图5-10(c)所示
第3步操作 V1、V2、V3 (V1,V3)
(V3,V2)
V4 (V1,V4) 6
(V2,V4) 2
(V3,V4) 9
权值最小的边为(V2,V4),所以顶点V4进入集合U,边(V2,V4)进入集合TE
第3步结果 V1、V2、V3、V4 (V1,V3)
(V3,V2)
(V2,V4)
  最小生成树完成,如图5-10(d)所示

  2.克鲁斯卡尔算法
  (1)算法思想
  设连通网N=(V,{E})中,T=(V,TE)是存放MST的集合,其中TE是N中最小生成树中边的集合。
  ①算法开始时,TE为空,此时T是一个只有n个顶点,没有边的森林。
  ②考查图中满足以下条件的边:边的一端在森林TE中的一棵树中,另一端在森林TE的另一棵树中,在这些边中寻找权值最小的一条。假设为(Vi,Vj),那么将边(Vi,Vj)加入集合TE中,这样将把T中两棵相对较小的树合成一棵相对较大的树,使得T中树的总数减小1个。
  ③重复执行步骤②共n-1次,T即为所求。
  (2)算法实例
  用克鲁斯卡尔算法求图5-11(a)的最小生成树。

  初始时TE为空,其余步骤如表5-6所示。

表5-6 克鲁斯卡尔算法求最小生成树步骤

 

TE

T中树的顶点

连接两棵树的边及其权值

说    明

第1步操作 {V1}{V2}
{V3}{V4}
(V1,V2) 5  (V1,V3) 1
(V1,V4) 6  (V2,V3) 3
(V2,V4) 2  (V3,V4) 9
权值最小的边为(V1,V3),将之加入到集合TE当中
第1步结果 (V1,V3) {V1,V3}
{V2}{V4}
  如图5-11(b)所示
第2步操作 (V1,V3) {V1,V3}
{V2}{V4)
(V1,V2) 5  (V1,V4) 6
(V2,V3) 3  (V2,V4) 2
(V3,V4) 9
权值最小的边为(V2,V4)
第2步结果 (V1,V3)
(V2,V4)
{V1,V3}
{V2,V4}
  如图5-11(c)所示
第3步操作 (V1,V3)
(V2,V4)
{V1,V3}
{V2,V4}
(V1,V2) 5  (V1,V4) 6
(V2,V3) 3  (V3,V4) 9
权值最小的边为(V2,V3)
第3步结果 (V1,V3)
(V2,V4)
(V2,V3)
{V1,V2,
V3,V4}
  最小生成树完成,如图5-11(d)所示

  3.算法分析
  普里姆算法根据顶点进行遍历,其时间复杂度为,与图中边数无关,该算法适合于求稠密网的最小生成图。
  克鲁斯卡尔算法根据边进行遍历,其时间复杂度为O(eloge),与图中顶点数无关,该算法适用于求稀疏网的最小生成树。

5.5 最小(代价)生成树★3◎4

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部