5.5 最小（代价）生成树★3◎4

5.5 最小（代价）生成树★3◎4　　如果连通图G的一个子图是一棵包含图G的所有顶点的树，则该子图称为G的“生

作者

次阅读

2010-11-16

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