单元实验五.pptx

,西安电子科技大学软件学院,-School of,Computer S,oftware,Xidian University,China,#,生成树的概念,生成树,一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的,n-1,条边。,生成树不唯一,V,3,V,2,V,4,V,1,V,6,V,5,V,3,V,2,V,4,V,1,V,6,V,5,V,3,V,2,V,4,V,1,V,6,V,5,V,3,V,2,V,4,V,1,V,6,V,5,生成树,最小代价生成树,生成树的代价等于其边上的权值之和。,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,V,4,V,1,V,3,V,2,V,6,V,5,6,1,6,5,4,V,4,V,1,V,3,V,2,V,6,V,5,1,2,5,3,4,最小代价生成树,两种常用的构造最小生成树的方法：,普里姆算法,克鲁斯卡尔算法,假设,N=(V,，,E),是连通网，,TE,是,N,上最小生成树中边的集合。,算法从,U=u,0,(u,0,V),，,TE=,开始，重复执行下述操作：,在所有,uU,，,vV-U,的边,(u,，,v),中找一条代价最小的边,(u,0,v,0,),将其并入集合,TE,，同时将,v,0,并入,U,集合。,当,U=V,则结束，此时,TE,中必有,n-1,条边，则,T=(V,，,TE),为,N,的最小生成树。,普里姆算法构造最小生成树的过程是从一个顶点,U=u,0,作初态，不断寻找与,U,中顶点相邻且代价最小的边的另一个顶点，扩充到,U,集合直至,U=V,为止。,普里姆,(Prim),算法,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,V,4,V,1,V,3,V,2,V,6,V,5,1,2,5,3,4,U,V-U,V,1,V,2,V,3,V,4,V,5,V,6,步骤,(0),V,1,V,3,V,2,V,4,V,5,V,6,(1),V,1,V,3,V,6,V,2,V,4,V,5,(2),V,1,V,3,V,6,V,4,V,2,V,5,(3),V,1,V,3,V,6,V,4,V,2,V,5,(4),V,1,V,3,V,6,V,4,V,2,V,5,(5),最小代价生成树,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,V,4,V,1,V,3,V,2,V,6,V,5,1,6,5,V,1,V,3,1,V,1,V,2,V,3,V,4,V,5,V,6,步骤,(0),V,1,V,3,V,2,V,4,V,5,V,6,(1),U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,V,4,V,1,V,3,V,2,V,6,V,5,6,5,V,1,V,3,1,V,1,V,2,V,3,V,4,V,5,V,6,步骤,(0),V,1,V,3,V,2,V,4,V,5,V,6,(1),V,6,V,1,V,3,V,6,V,2,V,4,V,5,(2),4,6,5,5,4,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,V,4,V,1,V,3,V,2,V,6,V,5,6,5,V,4,V,1,V,3,1,V,1,V,2,V,3,V,4,V,5,V,6,步骤,(0),V,1,V,3,V,2,V,4,V,5,V,6,(1),V,6,V,1,V,3,V,6,V,2,V,4,V,5,(2),4,6,5,5,V,1,V,3,V,6,V,4,V,2,V,5,(3),2,6,2,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,V,4,V,1,V,3,V,2,V,6,V,5,6,V,4,V,1,V,3,1,V,1,V,2,V,3,V,4,V,5,V,6,步骤,(0),V,1,V,3,V,2,V,4,V,5,V,6,(1),V,2,V,6,V,1,V,3,V,6,V,2,V,4,V,5,(2),4,6,5,V,1,V,3,V,6,V,4,V,2,V,5,(3),6,2,V,1,V,3,V,6,V,4,V,2,V,5,(4),5,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,V,4,V,1,V,3,V,2,V,6,V,5,V,4,V,1,V,3,1,V,1,V,2,V,3,V,4,V,5,V,6,步骤,(0),V,1,V,3,V,2,V,4,V,5,V,6,(1),V,2,V,6,V,5,V,1,V,3,V,6,V,2,V,4,V,5,(2),4,6,V,1,V,3,V,6,V,4,V,2,V,5,(3),6,2,V,1,V,3,V,6,V,4,V,2,V,5,(4),5,V,1,V,3,V,6,V,4,V,2,V,5,(5),3,3,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,V,4,V,1,V,3,V,2,V,6,V,5,V,4,V,1,V,3,1,V,1,V,2,V,3,V,4,V,5,V,6,步骤,(0),V,1,V,3,V,2,V,4,V,5,V,6,(1),V,2,V,6,V,5,V,1,V,3,V,6,V,2,V,4,V,5,(2),4,V,1,V,3,V,6,V,4,V,2,V,5,(3),2,V,1,V,3,V,6,V,4,V,2,V,5,(4),5,V,1,V,3,V,6,V,4,V,2,V,5,(5),3,U,V-U,最小代价生成树,普里姆,(Prim),算法,生成树中只放置一个顶点,在关联生成树顶点的边中（即边的,一个顶点在生成树中，另一个顶点不在）,取权值最小者,将选中的边加入生成树，,同时将该边的关联顶点加入生成树中,生成树中顶点数小于,n?,是,否,结束,开始,基本要求,从键盘（或数据文件）输入图的信息，用普里姆算法求解给定无向连通图的最小生成树，最后输出最小生成树中的权值和所有的边，图的存储结构自行设定。,例如 下图的输出为,weight,：,15,(v1,v3)(v3,v6)(v6,v4)(v3,v2)(v2,v5),顶点集合如何表示？,最小边如何选择？,一个顶点加入,U,集合（生成树中）,如何表示？,struct,int adjvex;,double lowcost;,closedgeMAX_VERTEX_NUM;,closedgei.adjvex=k,closedgei.lowcost=0,顶点,i,与顶点,k,邻接,顶点,k,已经在,U,集合中,顶点,i,加入,U,集合时,普里姆算法的实现,adjvex,lowcost,v1,6,v1,1,v1,5,v1,v2,v3,v4,v5,v6,3,2,3,4,5,6,U,V-U,k,顶点,i,closedge,closedge2.adjvex=1,.lowcost=6,closedge3.adjvex=1,.lowcost=1,closedge4.adjvex=1,.lowcost=5,V,4,V,1,V,3,V,2,V,6,V,5,1,6,5,当,U,集合中加入一个新顶点时，,V-U,集合中的顶点到,U,的最小代价边可能会更新,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,U,集合的成员：,V-U,集合的成员：,adjvex,lowcost,v1,6,v1,1,v1,5,v1,v2,v3,v4,v5,v6,3,adjvex,lowcost,v3,5,0,v1,5,v3,6,v3,4,v1,v3,v2,v4,v5,v6,6,2,3,4,5,6,U,V-U,k,顶点,i,closedge,V,4,V,1,V,3,V,2,V,6,V,5,5,5,6,4,U,集合的成员：,V-U,集合的成员：,当,U,集合中加入一个新顶点时，,V-U,集合中的顶点到,U,的最小代价边可能会更新,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,adjvex,lowcost,v1,6,v1,1,v1,5,v1,v2,v3,v4,v5,v6,3,adjvex,lowcost,v3,5,0,v1,5,v3,6,v3,4,v1,v3,v2,v4,v5,v6,6,adjvex,lowcost,v3,5,0,v6,2,v3,6,0,v1,v3,v6,v2,v4,v5,4,2,3,4,5,6,U,V-U,k,顶点,i,closedge,V,4,V,1,V,3,V,2,V,6,V,5,5,6,2,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,当,U,集合中加入一个新顶点时，,V-U,集合中的顶点到,U,的最小代价边可能会更新,U,集合的成员：,V-U,集合的成员：,adjvex,lowcost,v1,6,v1,1,v1,5,v1,v2,v3,v4,v5,v6,3,adjvex,lowcost,v3,5,0,v1,5,v3,6,v3,4,v1,v3,v2,v4,v5,v6,6,adjvex,lowcost,v3,5,0,v6,2,v3,6,0,v1,v3,v6,v2,v4,v5,4,adjvex,lowcost,v3,5,0,0,v3,6,0,v1,v3,v6,v4,v2,v5,2,3,4,5,6,U,V-U,k,顶点,i,closedge,2,V,4,V,1,V,3,V,2,V,6,V,5,5,6,当,U,集合中加入一个新顶点时，,V-U,集合中的顶点到,U,的最小代价边可能会更新,U,集合的成员：,V-U,集合的成员：,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,adjvex,lowcost,v1,6,v1,1,v1,5,v1,v2,v3,v4,v5,v6,3,adjvex,lowcost,v3,5,0,v1,5,v3,6,v3,4,v1,v3,v2,v4,v5,v6,6,adjvex,lowcost,v3,5,0,v6,2,v3,6,0,v1,v3,v6,v2,v4,v5,4,adjvex,lowcost,v3,5,0,0,v3,6,0,v1,v3,v6,v4,v2,v5,2,adjvex,lowcost,0,0,0,v2,3,0,v1,v3,v6,v4,v2,v5,2,3,4,5,6,U,V-U,k,顶点,i,closedge,5,V,4,V,1,V,3,V,2,V,6,V,5,3,当,U,集合中加入一个新顶点时，,V-U,集合中的顶点到,U,的最小代价边可能会更新,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,U,集合的成员：,V-U,集合的成员：,adjvex,lowcost,v1,6,v1,1,v1,5,v1,v2,v3,v4,v5,v6,3,adjvex,lowcost,v3,5,0,v1,5,v3,6,v3,4,v1,v3,v2,v4,v5,v6,6,adjvex,lowcost,v3,5,0,v6,2,v3,6,0,v1,v3,v6,v2,v4,v5,4,adjvex,lowcost,v3,5,0,0,v3,6,0,v1,v3,v6,v4,v2,v5,2,2,3,4,5,6,U,V-U,k,顶点,i,closedge,V,4,V,1,V,3,V,2,V,6,V,5,adjvex,lowcost,0,0,0,0,0,v1,v3,v6,v4,v2,v5,adjvex,lowcost,0,0,0,v2,3,0,v1,v3,v6,v4,v2,v5,5,1,4,2,5,3,U,集合的成员：,V-U,集合的成员：,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,void MiniSpanTree_PRIM(Graph G,int u),/,用普里姆算法从顶点,u,出发构造,G,的最小生成树,for(j=0;j G.vexnum;+j),/,辅助数组初始化,if(j!=u)closedgej=u,G.arcsuj;,struct,int adjvex;,double lowcost;,closedgeMAX_VERTEX_NUM;,closedgeu.lowcost=0;,/,初始,U=u,for(i=1;i G.vexnum;+i),k=minimum(closedge);,/,求生成树的下一个顶点,k,cout closedgek.adjvex G.vexsk;,closedgek.lowcost=0;,for(j=0;j G.vexnum;+j),if(G.arcskj.adj 0,v,i,v-u,cout closedgek.adjvex G.vexsk;,/,输出生成树的边,closedge,k,.lowcost=0;,/,顶点,k,并入,U,集合,for(j=0;j G.vexnum;+j),if(G.arcskj closedgej.lowcost),closedgej.adjvex=k,closedgej.Lowcost=G.arcskj;,算法的时间复杂度为：,O(n,2,),closedgej.adjvex=u;closedgej.lowcost=G.arcsuj;,选做内容,从键盘输入（或从文件读入）图的信息，用克鲁斯卡尔算法求解给定无向连通图的最小生成树，最后输出最小生成树中的权值和所有的边。,克鲁斯卡尔,(Kruskal),算法,假设连通网,N=(V,，,E),，则令最小生成树的初始状态为只有,n,个顶点而无边的非连通图,T=(V,，,),，图中每个顶点自成一个连通分量。,在,E,中选择代价最小的边，若该边依附的顶点落在,T,中不同的连通分量上，则将此边加入到,T,中，否则舍去此边而选择下一条代价最小的边。依次类推，直至,T,中所有顶点都在同一连通分量上为止。,克鲁斯卡尔算法求最小生成树,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,V,4,V,1,V,3,V,2,V,6,V,5,1,2,3,4,最小代价生成树,克鲁斯卡尔算法求最小生成树,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,V,4,V,1,V,3,V,2,V,6,V,5,1,2,3,4,5,V,3,、,V,4,依附在同一个连通分量,最小代价生成树,克鲁斯卡尔算法求最小生成树,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,V,4,V,1,V,3,V,2,V,6,V,5,1,2,3,4,V,1,、,V,4,依附在同一个连通分量,5,最小代价生成树,克鲁斯卡尔算法求最小生成树,V,4,V,1,V,3,V,2,V,6,V,5,6,5,1,2,6,6,5,5,3,4,V,4,V,1,V,3,V,2,V,6,V,5,1,2,5,3,4,最小代价生成树,克鲁斯卡尔,(Kruskal),算法,否,将堆顶的边加入生成树后,是否形成回路,?,在生成树中放置,n,个孤立顶点,根据边上的权值建小顶堆,是,将该边加入生成树中,去掉堆顶元素，,剩余元素重新建堆,生成树中边数小于,n-1?,是,否,结束,开始,克鲁斯卡尔,(Kruskal),算法,从上述过程可知，实现,克鲁斯卡尔,(Kruskal),算法时，要解决以下两个问题：,如何选择代价最小的边,(,堆排序，或简单选择排序,),；,如何判定边所关联的两个顶点是否在同一个连通分量中（集合）,End,