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),与图中顶点数无关,该算法适用于求稀疏网的最小生成树。
评论列表 人参与