《数据结构-最小生成树.ppt》由会员分享，可在线阅读，更多相关《数据结构-最小生成树.ppt（49页珍藏版）》请在三一办公上搜索。
1、最小生成树,生成树和生成森林,最小生成树,*关节点和重连通分量,小结和作业,遍历应用举例,图的遍历应用举例,1.求一条从顶点i到顶点s的简单路径,2.求两个顶点之间的一条长度最短的路径,图的遍历应用举例,1.求一条从顶点i到顶点s的简单路径,求从顶点b到顶点k的一条简单路径。,从顶点b出发进行深度优先搜索遍历,图的遍历应用举例,求从顶点b到顶点k的一条简单路径。,假设找到的第一个邻接点是a,且得到的结点访问序列为:b a c h d e k f g,假设找到的第一个邻接点是g,则得到的结点访问序列为:b g f k e a d h c,图的遍历应用举例,1.从顶点 i 到顶点s,若存在路径，则
2、从顶点 i 出发进行深度优先搜索，必能搜索到顶点s。,2.简单路径可能有多条。,3.由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。,结论：,图的遍历应用举例,void DFSearch(int v,int s,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个顶点加入路径
3、,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,广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。,广度优先搜索是使用“队列”实现的，如何记住路径的所有结点？,图的遍历应用举例,图的遍历应用举例,0 A1 B2 C 3 D4
4、E5 F G K,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);/for if(found)break;/while/从w开始往后找祖先结点，逆向打印,生成树,一、定义图G的生成树是G的极小连通子图，即包含G中的所有顶点（n
5、）和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 个城
6、市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？,问题：,最小生成树,连通网：n个城市和城市间可能的通信线路,网的顶点：表示城市,网的边：表示两个城市之间的线路,网的边上的权值：通信代价,最小生成树,构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。,算法二：（克鲁斯卡尔算法）,该问题等价于：,算法三：（普里姆算法）,算法一：（破圈法）,破圈法,一、基本思想1、如果图G是一个连通图，但不是树，则边数n-1，图中一定存在回路（环/圈）。2、将所有的边按权重从大到小排列3、对每条边e尝试下面的操
7、作，直到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,
8、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具有最短边的顶点,
9、1、对任何一个顶点v，如果它有多个邻接U的边，则需要找出最短的边作为邻接到U的边,2、从所有的V U顶点中，找出具有最短边的顶点，将它加入U,普里姆算法,技巧：设置一个辅助数组，对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：,struct VertexType adjvex;/U集中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTEX_NUM;,普里姆算法,初始时U=v0,对wV U，closedgew.lowcost=或者=closedgew.adjvex=v0,当U=U u时，,对wV U，修改closedgew,closedge
10、w.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,普里姆算法,void MiniSpanTree_P(MGraph G,VertexType u)/用普里姆算法从顶点u出发构造网G的最小生成树 k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，Uu for(i=0;iG.vexnum
11、;+i),继续向生成树上添加顶点;,普里姆算法,k=minimum(closedge);/求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk,closedgek.lowcost);/输出生成树上一条边 closedgek.lowcost=0;/第k顶点并入U集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边 if(G.arcskj.adj closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;,两种算法的比较,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(eloge),稠密图,稀
12、疏图,算法名称,适应范围,课堂练习,求出图中最小生成树,关节点和重连通图,若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。,问题：,关节点和重连通图,若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。,没有关节点的连通图为双连通图。,如何判别给定的连通图是否是双连通图？,关节点和重连通图,a,h,g,c,b,f,d,e,下列连通图中，,顶点a和顶点c是关节点,关节点和重连通图,1,2,3,4,5,6,7,8,3,3,1,1,1,1,1,1,深度优先生成树,关节点和重连通图,关节点有何
13、特征？,若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点;,对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。,关节点和重连通图,对上述两个判定准则在算法中如何实现？,关节点和重连通图,1)设V0为深度优先遍历的出发点 p=G.vertices0.firstarc;v=p-adjvex;DFSArticul(G,v);/从第v顶点出发深度优先搜索 if(count G.vexnum)/生成树的根有至少两棵子树 printf(0,G.vertices0.data);/根是关节点,关节点和重连通图,2)定义
14、函数:low(v)=Minvisitedv,loww,visitedk 其中:顶点w 是生成树上顶点v 的孩子;顶点k 是生成树上和顶点v由回边 相联接的祖先;visited记录深度优先遍历时的访问次序 若对顶点v，在生成树上存在一个子树根w,且 loww visitedv 则顶点v为关节点。,关节点和重连通图,对深度优先遍历算法作如下修改：,1。visitedv的值改为遍历过程中顶点的访问次序count值;,2。遍历过程中求得 lowv=Minvisitedv,loww,visitedk,3。从子树遍历返回时，判别lowwvisitedv?,关节点和重连通图,void DFSArticul(
15、ALGraph G,int v0)/从第v0个顶点出发深度优先遍历图G,查找并输出关节点/DFSArticul,for(p=G.verticesv0.firstarc;p;p=p-nextarc),min=visitedv0=+count;/v0是第count个访问的顶点,并设lowv0的初值为min,/检查v0的每个邻接点,lowv0=min;,关节点和重连通图,w=p-adjvex;/w为v0的邻接顶点 if(visitedw=0)/w未曾被访问 DFSArticul(G,w);/返回前求得loww else/w是回边上的顶点,if(loww min)min=loww;,if(loww=visitedv0)printf(v0,G.verticesv0.data);/输出关节点,if(visitedw min)min=visitedw;,小结和作业,1.普里姆算法,2.克鲁斯卡尔算法,3.两种算法的比较,2.最小生成树算法,1.图的生成树和生成森林,作业：7.7,生成森林,void DFSTree(Graph G,int v,CSTree/end of if/end of DFSTree,生成森林,二、算法以孩子兄弟链表作为生成森林的存储结构,void DFSForest(Graph G,CSTree,
