最小生成树算法实验报告.doc

最小生成树算法问题描述设G=(V,E)是一个无向连通带权图,E中每条边(v,w)的权为c(v,w)。如果G的一个子图G`是一棵包含G的所有顶点的书,则称G`为G的生成树。生成树上各边权的总和称为该生成树的耗费,在G的所有生成树中,耗费最小的生成树就称为G的最小生成树。给定一个无向连通带权图,构造一个最小生成树。设计思想利用Prim算法求最小生成树,Prim算法是利用贪心策略设计的算法。设G=(V,E)是一个连通带权图,V={1,2,…,n}。构造G的一棵最小生成树的Prim算法的基本思想是:首先置U={1},然后,只要U是V的真子集,就做如下的贪心选择:选取满足条件i∈U,j∈V-U,且使c(i,j)达到最小的边(i,j),并将顶点j添加到U中。这个过程一致进行到U=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。时间复杂度Prim算法的Pascal语言描述如下:ProcedurePRIM(c:array[1..n,1..n]ofreal);Var lowcost:array[1..n]ofreal; closest:array[1..n]ofinteger; i,j,k,min,integer;beginfori:=2tondobegin{初始化,此时U只含有顶点1}lowcost[i]:=c[1,i];Closest[i]:=1;end;fori:=2tondobegin{寻找顶点分别在V-U与U中边权最小的边}min:=lowcost[i];j:=i;Fork:=2tondoIflowcost[k]<minthenBeginMin:=lowcost[k];j:=k;End;print(j,closest[j]);{输出找到的边}Lowcost[j]:=∞;{将j添加到U}Fork:=2tondo{调整lowcost和closest}if(c[j,k]<lowcost[k])and(lowcost[k]<∞)thenBeginLowcost[k]:=c[j,k];Closest[k]:=j;EndEndEnd;{PRIM}上述过程中第(6)~(24)行的for循环要执行n-1次,每次执行时,第(10)~(15)行和第(18)~(23)行的for循环都要O(n)时间,所以Prim算法所需的计算时间为O(n)。:constintMaxV=10;//最多顶点数constintMaxValue=99;//最大权值//定义边集数组中的元素类型structRCW{introw,col;intweight;};classadjMList{private:intnumE;//当前边数intGA[MaxV][MaxV];//定义邻接矩阵public://构造函数,初始化图的邻接矩阵与边集数组adjMList(RCWGE[],intn,inte);//建立无向带权图的邻接矩阵voidCreateMatrix(intn,int&e,RCWr[]);//输出边集数组中的每条边voidOutputEdgeSet(RCWge[],inte);//根据图的邻接矩阵生成图的边集数组voidChangeEdgeSet(RCWGE[],intn,inte);//按升序排列图的边集数组voidSortEdgeSet(RCWGE[],