第14讲 图的生成树

第十四讲图的生成树主讲：朱郑州《数据结构》DataStructure主要内容2.Prim算法1.图的连通性3.Kruskal算法要想判定一个无向图是否为连通图，或有几个连通分量，通过对无向图遍历即可得到结果。非连通图：需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。连通图：仅需从图中任一顶点出发，进行深度优先搜索（或广度优先搜索），便可访问到图中所有顶点。无向图的连通性count=0;2.for(图中每个顶点v)2.1if(v尚未被访问过)2.1.1count++;2.1.2从v出发遍历该图；3.if(count==1)printf("图是连通的“);elseprintf("图中有count个连通分量");求无向图的连通分量无向图的连通性⑴从某顶点出发进行深度优先遍历，并按其所有邻接点都访问（即出栈）的顺序将顶点排列起来。⑵从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历。若不能访问到所有顶点，则从余下的顶点中最后访问的那个顶点出发，继续作逆向的深度优先遍历，直至有向图中所有顶点都被访问到为止。⑶每一次逆向深度优先遍历所访问到的顶点集便是该有向图的一个强连通分量的顶点集。有向图的连通性（a）深度优先生成树（b）广度优先生成树V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8图的生成树由深度优先遍历得到的为深度优先生成树，由广度优先遍历得到的为广度优先生成树。一个连通图的生成树可能不唯一，由不同的遍历次序、从不同顶点出发进行遍历都会得到不同的生成树。对于非连通图，通过图的遍历，将得到的是生成森林。结论：图的生成树生成树的代价：设G=（V，E）是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。最小生成树(MinimumSpanningTree,MST)：在图G所有生成树中，代价最小的生成树称为最小生成树。最小生成树的概念可以应用到许多实际问题中。例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？最小生成树假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。顶点集UV－Uu'vv'u顶点集T1T2最小生成树性质主要内容2.Prim算法1.图的连通性3.Kruskal算法基本思想：设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树，T的初始状态为U={u0}（u0∈V），TE={}，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u,v)并入集合TE，同时v并入U，直至U=V。关键:是如何找到连接U和V-U的最短边。利用MST性质，可以用下述方法构造候选最短边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。普里姆（Prim）算法U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725ABEDCF普里姆（Prim）算法251234192646381725ABEDCFU={A,F}V-U={B,C,D,E}cost={(A,B)34,(F,C)25,(F,D)25,(F,E)26}普里姆（Prim）算法251234192646381725ABEDCFU={A,F,C}V-U={B,D,E}cost={(A,B)34,(C,D)17,(F,E)26}

普里姆（Prim）算法251234192646381725ABEDCFU={A,F,C,D}V-U={B,E}cost={(A,B)34,(F,E)26}

普里姆（Prim）算法251234192646381725ABEDCFU={A,F,C,D,E}V-U={B}cost={(E,B)12}

普里姆（Prim）算法251234192646381725ABEDCFU={A,F,C,D,E,B}V-U={}普里姆（Prim）算法数组lowcost[n]：用来保存集合V-U中各顶点与集合U中顶点最短边的权值，lowcost[v]=0表示顶点v已加入最小生成树中；数组adjvex[n]：用来保存依附于该边（集合V-U中各顶点与集合U中顶点的最短边）在集合U中的顶点。数据结构设计表示顶点vi和顶点vk之间的权值为w，其中：vi∈V-U且vk

∈Ulowcost[i]=wadjvex[i]=k如何用数组lowcost和adjvex表示候选最短边集？普里姆（Prim）算法

i

数组B(i=1)C(i=2)D(i=3)E(i=4)F(i=5)UV-U输出adjvexlowcostA34A46A∞A∞A19{A}{B,C,D,E,F}(AF)19adjvexlowcostA34F25F25F26

{A,F}{B,C,D,E}(FC)25adjvexlowcostA34

C17F26

{A,F,C}{B,D,E}(CD)17adjvexlowcostA34

F26

{A,F,C,D}{B,E}(FE)26adjvexlowcostE12

{A,F,C,D,E}{B}(EB)12adjvexlowcost

{A,F,C,D,E,B}{}

普里姆（Prim）算法1.初始化两个辅助数组lowcost和adjvex；2.输出顶点u0，将顶点u0加入集合U中；3.重复执行下列操作n-1次

3.1在lowcost中选取最短边，取adjvex中对应的顶点序号k；

3.2输出顶点k和对应的权值；

3.3将顶点k加入集合U中；

3.4调整数组lowcost和adjvex；Prim算法——伪代码

普里姆（Prim）算法主要内容2.Prim算法1.图的连通性3.Kruskal算法基本思想：设无向连通网为G＝(V,E)，令G的最小生成树为T＝(U,TE)，其初态为U＝V，TE＝{}，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。克鲁斯卡尔（Kruskal）算法251234192646381725ABEDCFABEDCF连通分量＝{A},{B},{C},{D},{E},{F}克鲁斯卡尔（Kruskal）算法251234192646381725ABEDCFABEDCF连通分量＝{A},{B},{C},{D},{E},{F}12连通分量＝{A},{B,E},{C},{D},{F}克鲁斯卡尔（Kruskal）算法251234192646381725ABEDCFABEDCF12连通分量＝{A},{B,E},{C},{D},{F}克鲁斯卡尔（Kruskal）算法17连通分量＝{A},{B,E},{C,D},{F}251234192646381725ABEDCFABEDCF连通分量＝{A},{B,E},{C,D},{F}12连通分量＝{A,F},{B,E},{C,D}19克鲁斯卡尔（Kruskal）算法17251234192646381725ABEDCFABEDCF连通分量＝{A,F},{B,E},{C,D}12连通分量＝{A,F,C,D},{B,E}191725克鲁斯卡尔（Kruskal）算法251234192646381725ABEDCFABEDCF连通分量＝{A,F,C,D},{B,E}12连通分量＝{A,F,C,D,B,E}19172526克鲁斯卡尔（Kruskal）算法1.初始化：U=V；TE={}；2.循环直到T中的连通分量