(7.4.1)-7.4图的连通性与最小生成树

图的最小生成树1

7.4图的最小生成树（MinimumSpinningTree）相关概念克鲁斯卡尔Kruskal算法普里姆Prim算法光纤通信网络问题31654327131791812752410要在n个城市间建立通信联络网，使总造价最低。其中：顶点——表示城市权——城市间建立通信线路所需花费代价7.4生成树定义：（连通图）所有顶点均由边连接在一起，但不存在回路的图叫生成树深度优先生成树与广度优先生成树生成森林：非连通图每个连通分量的生成树一起组成非连通图的生成森林说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图(保证连通的最少边数)一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树51234

含n个顶点n-1条边不是生成树的图

不唯一的最小生成树V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林最小生成树所有生成树中，各条边权值之和最小的生成树（最小代价生成

树）。求解思路在可能的线路中选择n-1条，能把所有城市（顶点）连结起来，

且总耗费（各边权值之和）最小MST性质（构造最小生成树的理论依据,贪心算法，局部最优导致全局最优）描述：假设N=（V，{E}）是一个连通网，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边（u，v）的最小生成树。9证明：

假设网N的任何一棵最小生成树都不包含（u，v）。设T是连通网上的一棵最小生成树，当边（u，v）加入到T中时，由生成树的定义，T中必存在一条包含（u，v）的回路。另一方面，由于T是生成树，则在T上必存在另一条边（u’，v’），其中u’∈U，v’∈V-U，且u和u’之间，v和v’之间均有路径相通。删去边（u’，v’），便可消除上述回路，同时得到另一棵生成树T’。因为（u，v）的代价不高于（u’，v’），则T’的代价亦不高于T，T’是包含（u，v）的一棵最小生成树。由此和假设矛盾。构造最小生成树方法方法一：普里姆(Prim)算法假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={uo}（uo∈V），TE{}开始，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边（u，v）∈E并入集合TE，同时v并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{TE}）为N的最小生产树。算法实现：图用邻接矩阵表示算法评价：T(n)=O(n²)Prim算法流程图11选择备选边信息表中权重最小的边(u,v)删除备选边信息表中所有以v为头的边，更新以集合U-V中顶点为头的边V=V+{v}选择起点v0，初始化备选边信息表为关联于v0的边（或弧）重复n-1步例1654326513566425131163141643142116432142516543214253方法二：克鲁斯卡尔(Kruskal)算法算法思想：设连通网N=(V,{E})，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边依此类推，直至T中所有顶点都在同一连通分量上为止例165432651356642516543212345（0）用顶点数组和边数组存放顶点和边信息（1）初始时，每个顶点的set互不相同（set表示连通分量编号）；每个边的flag为0（表示未选入最小生成树）（2）选出权值最小且flag为0的边（3）若该边依附的两个顶点的set值不同，即非连通，则令该边的flag=1,选中该边；再令该边依附的两顶点的set

以及两集合中所有顶点的set相同（连通分量合并，取小set

值），若该边依附的两个顶点的set值相同，即连通，则令该边的flag=2,即舍弃该边（4）重复上述步骤，直到选出n-1条边为止顶点结点：typedefstruct{intdata;//顶点信息

intset;//连通分量信息}VEX;边结点：typedefstruct{intvexh,vext;//边依附的两顶点

intweight;//边的权值

intflag;//标志域}EDGE;例1654326513566425算法描述：vexhweight112213233544vextflag6153550000000134256789334556666426000011111216543212345datasetsetsetsetsetset1122133144155216641构造顺序最小生成树小结：1.最小生成树可能不唯一2.普里姆Prim算法从顶点出发