最小生成树.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,四、最小生成树,(minimum cost spanning tree),连通图,G,的一个子图如果是一棵包含,G,的所有顶点的树，则该子图称为,G,的,生成树,。,生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。,生成树各边的权值总和称为生成树的权。权最小的生成树称为,最小生成树,用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。,按照生成树的定义，,n,个顶点的连通网络的生成树有,n,个顶点、,n,-,1,条边。,构造最小生成树的准则：,必须只使用该网络中的边来构造最小生成树；,必须使用且仅使用,n,-,1,条边来联结网络中的,n,个顶点；,不能使用产生回路的边。,最小生成树（,MST,minimal spanning tree,）的重要性质：,设,G=,（,V,，,E,）,是一个连通网络，,U,是顶点集,V,的,一个非空子集。,若（,u,，,v,）,是一条具有最小权值（代价）的边，,其中,u,U,v,V,-U,则一定存在,G,的一棵包括（,u,，,v,）的最小生成树。,u,v,U,VU,证明（反证法）：,假设,G,中任何一棵最小生成树中都不包含,(u,，,v),。设,T,是一棵最小生成树但不包含,(u,，,v),。,由于,T,是最小生成树，所以,T,是连通的，因此有一条从,u,到,v,的路径，且该路径上必有一条连接两个顶点集,U,、,V,的边,(,u,，,v,),，,其中,u,U,，,v,V-U,。,当把边,(u,，,v),加入到,T,中后，得到一个含有边,(u,，,v),的回路。删除边,(,u,，,v,),，,上述回路即被消除。由此得到另一棵生成树,T,，,T,和,T,的区别仅在于用边,(u,，,v),代替了,(,u,，,v,),。,由于,(u,，,v),的权,=(,u,，,v,),的全权，所以，,T,的权,=T,的权，与假设矛盾。,u,v,U,VU,u,v,普里姆,(Prim),算法,普里姆算法的基本思想：,从连通网络,N,=,V,E,中的某一顶点,u,0,出,发，选择与它关联的具有最小权值的边,(,u,0,v,),，,将其顶点加入到,生成树的顶点集合,U,中。以后每,一步从,一个顶点在,U,中,，而,另一个顶点不在,U,中,的各条边中选择,权值最小的边,(,u,v,),把它的顶点,加入到,集合,U,中。如此继续下去，直到网络中的,所有顶点都加入到生成树顶点集合,U,中为止。,用普里姆,(Prim),算法构造最小生成树的过程,1,2,3,4,6,5,5,6,5,1,7,3,2,5,4,6,1,2,3,4,6,5,5,1,3,2,4,从节点开始，选最小权值的边,1,，节点（，,）入,U;,从,U,中选最小权值边,5,，且对应节点不在,U,中，入,U;,从,U,中选最小权值边,3,，且对应节点不在,U,中，,入,U;,从,U,中选最小权值边,4,，且对应节点不在,U,中，,入,U;,从,U,中选最小权值边,2,，且对应节点不在,U,中，,入,U;,普里姆算法构造的基本思想,为直观解释方便，设想在构造过程中，,T,的,顶点集,U,和边集均被涂成红色，,U,之外的顶点涂,成蓝色，连接红点和蓝点的边被涂成紫色。因,此，最短紫边就是连接,U,和,V-U,的最短边。,设当前生成的,T,有,k,个顶点，则当前紫边数目,是,k(n-k),，,紫边集过大。为了构造一个较小的,侯选紫边集，可以这样处理：对每一个蓝点，,从该蓝点到红点的紫边中，必有一条是最短的,，我们只要将所有,n-k,个蓝点所关联的最短紫边,作为侯选集，就必定能保证所有紫边中最短的,紫边属于该侯选集。,侯选集的调整方法：,当最短紫边,(u,v),被涂成红色被加入,T,中后，,v,由,蓝点变为红点，对每一个剩余的蓝点,j,，边,(v,j),就由非,紫边变成了紫边，这就使得我们必须对侯选集做如下调整：若侯选集中蓝点,j,所关联的原最短紫边长度大于新紫边,(v,j),的长度，则以,(v,j),作为,j,所,关联的新的最短紫边来代替,j,的原,最短紫边，否则,j,的原最短紫边不变。,Prim,算法的结构如下：,(1),置,T,为任意一个顶点，置初始侯选紫边集；,(2)while(T,中顶点数目,n),(3),从侯选紫边集中选取最短紫边,(u,v);,(4),将,(u,v),及,蓝点,v,涂成红色，扩充到,T,中；,(5),调整侯选紫边集；,(6),PRIM,算法,typedef,struct,int,fromvex,endvex,;,float length;,edge;,float distnn;,edge Tn-1;,PRIM(),int,j,k,m,v,min,max=10000;,float d;,edge e;,for(j=1;jn;j+),Tj-1.fromvex=1;,Tj-1.endvex=j+1;,Tj-1.length=dist0j;,for(k=0;kn-1;k+),min=max;,for(j=k;jn-1;j+),if(Tj.lengthmin),min=Tj.length;,m=j;,e=Tm;Tm=Tk;Tk=e;,v=,Tk.endvex,;,for(j=k+1;jn-1;j+),d=distv-1Tj.endvex-1;,if(dTj.length),Tj.length=d;,Tj.fromvex,=v;,算法分析,上述算法的初始化时间是,O(1),，,k,循环中有两个循环语句，其时间大致为：,令,O(1),为某一,正常数,C,，,展开上述求和公式可知其数量级仍是,n,的平方。所以，整个算法的时间复杂性是,O(n,2,),