数据结构-最小生成树.ppt

最小生成树,生成树和生成森林,最小生成树,*关节点和重连通分量,小结和作业,遍历应用举例,图的遍历应用举例,1.求一条从顶点i到顶点s的简单路径,2.求两个顶点之间的一条长度最短的路径,图的遍历应用举例,1.求一条从顶点i到顶点s的简单路径,求从顶点b到顶点k的一条简单路径。,从顶点b出发进行深度优先搜索遍历,图的遍历应用举例,求从顶点b到顶点k的一条简单路径。,假设找到的第一个邻接点是a,且得到的结点访问序列为:bachdekfg,假设找到的第一个邻接点是g,则得到的结点访问序列为:bgfkeadhc,图的遍历应用举例,1.从顶点i到顶点s,若存在路径，则从顶点i出发进行深度优先搜索，必能搜索到顶点s。,2.简单路径可能有多条。,3.由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。,结论：,图的遍历应用举例,voidDFSearch(intv,ints,char*PATH)/从第v个顶点出发递归地深度优先遍历图G，/求得一条从v到s的简单路径，并记录在PATH中visitedv=TRUE;/访问第v个顶点for(w=FirstAdjVex(v);w=0;w=NextAdjVex(v)if(!visitedw)DFSearch(w,s,PATH);,Append(PATH,getVertex(v);/第v个顶点加入路径,if(w=s)found=TRUE;Append(PATH,w);break;else,if(!found)Delete(PATH);/从路径上删除顶点v,图的遍历应用举例,2.求两个顶点之间的一条长度最短的路径,若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?,图的遍历应用举例,求从顶点b到顶点k的一条路径长度最短的路径。,图的遍历应用举例,a,b,c,h,d,e,k,f,g,广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。,广度优先搜索是使用“队列”实现的，如何记住路径的所有结点？,图的遍历应用举例,图的遍历应用举例,0A1B2C3D4E5FGK,1,-1,1,0,0,0,1,a,b,c,h,d,e,k,f,g,1,图的遍历应用举例,怎样修改广度优先遍历算法呢？,while(!QueueEmpty(Q)DeQueue(Q,u);for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)w.parent=u;if(w=?)found=true;break;if(!visitedw)visitedw=TRUE;EnQueue(Q,w);/forif(found)break;/while/从w开始往后找祖先结点，逆向打印,生成树,一、定义图G的生成树是G的极小连通子图，即包含G中的所有顶点（n）和n-1条边的连通子图,生成树,V1,V2,V4,V8,V5,V3,V6,V7,V1,V2,V3,V4,V5,V8,V6,V7,深度优先：,广度优先：,生成树,二、算法图的遍历算法访问了图中的每个顶点一次且仅一次。访问某个顶点的邻接点时，要经过与这两个顶点相关联的边。,因此，图的遍历算法可以产生一颗生成树：所有的顶点和经过的边。,生成森林,一、定义非连通图G的每个连通分量的生成树，构成了图G的生成森林,生成森林,8,1,2,3,4,5,6,7,0,a,c,h,d,k,f,e,b,g,a,b,c,h,d,e,k,f,g,非连通图G：,G的深度优先搜索生成森林：,最小生成树,假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？,问题：,最小生成树,连通网：n个城市和城市间可能的通信线路,网的顶点：表示城市,网的边：表示两个城市之间的线路,网的边上的权值：通信代价,最小生成树,构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。,算法二：（克鲁斯卡尔算法）,该问题等价于：,算法三：（普里姆算法）,算法一：（破圈法）,破圈法,一、基本思想1、如果图G是一个连通图，但不是树，则边数n-1，图中一定存在回路（环/圈）。2、将所有的边按权重从大到小排列3、对每条边e尝试下面的操作，直到G中的边数=n-1如果删除e,图G仍然是连通图，则从G中删除e，否则，保留e。,破圈法,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,12,7,二、示例(venum=7,arcnum=11,67),克鲁斯卡尔算法,具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,克鲁斯卡尔算法,a,b,c,d,e,g,f,3,a,b,c,e,g,f,d,21,5,8,14,16,克鲁斯卡尔算法,算法描述:,构造非连通图ST=(V,);k=i=0;/k选中的边数while(kn-1)+i;检查边集E中第i条权值最小的边(u,v);if若(u,v)加入ST后不使ST中产生回路，则输出边(u,v);且k+;,普里姆算法,在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,普里姆算法,a,b,e,g,f,14,d,8,c,3,5,16,21,g,b,d,g,b,f,c,普里姆算法,算法的核心：选择向集合U中加入的顶点时，要选择到U具有最短边的顶点,1、对任何一个顶点v，如果它有多个邻接U的边，则需要找出最短的边作为邻接到U的边,2、从所有的VU顶点中，找出具有最短边的顶点，将它加入U,普里姆算法,技巧：设置一个辅助数组，对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：,structVertexTypeadjvex;/U集中的顶点序号VRTypelowcost;/边的权值closedgeMAX_VERTEX_NUM;,普里姆算法,初始时U=v0,对wVU，closedgew.lowcost=或者=closedgew.adjvex=v0,当U=Uu时，,对wVU，修改closedgew,closedgew.lowcost=或者不变closedgew.adjvex=u,普里姆算法,a,e,d,c,b,a,a,a,19,14,18,14,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,普里姆算法,voidMiniSpanTree_P(MGraphG,VertexTypeu)/用普里姆算法从顶点u出发构造网G的最小生成树k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，Uufor(i=0;iG.vexnum;+i),继续向生成树上添加顶点;,普里姆算法,k=minimum(closedge);/求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk,closedgek.lowcost);/输出生成树上一条边closedgek.lowcost=0;/第k顶点并入U集for(j=0;jadjvex;/w为v0的邻接顶点if(visitedw=0)/w未曾被访问DFSArticul(G,w);/返回前求得lowwelse/w是回边上的顶点,if(loww=visitedv0)printf(v0,G.verticesv0.data);/输出关节点,if(visitedwmin)min=visitedw;,小结和作业,