最小生成树算法实验报告

《最小生成树算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最小生成树算法Ø问题描述设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的真子集，就做

2、如下的贪心选择：选取满足条件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);Varlowcost:array[1..n]ofreal;closest:array[1..n]ofinteger;i,j,k,min,integer;begin(1)fori:=2tondo(2)begin{初始化，此

3、时U只含有顶点1}(3)lowcost[i]:=c[1,i];(4)Closest[i]:=1;(5)end;(6)fori:=2tondo(7)begin{寻找顶点分别在V-U与U中边权最小的边}(8)min:=lowcost[i];(9)j:=i;(10)Fork:=2tondo(11)Iflowcost[k]

4、Fork:=2tondo{调整lowcost和closest}(19)if(c[j,k]

5、xV=10;//最多顶点数constintMaxValue=99;//最大权值//定义边集数组中的元素类型structRCW{introw,col;intweight;};classadjMList{private:intnumE;//当前边数intGA[MaxV][MaxV];//定义邻接矩阵public://构造函数,初始化图的邻接矩阵与边集数组adjMList(RCWGE[],intn,inte);//建立无向带权图的邻接矩阵voidCreateMatrix(intn,int&e,RCWr[]);//输出边集数组中的每条边voidOut

6、putEdgeSet(RCWge[],inte);//根据图的邻接矩阵生成图的边集数组voidChangeEdgeSet(RCWGE[],intn,inte);//按升序排列图的边集数组voidSortEdgeSet(RCWGE[],inte);//利用普里姆算法从顶点v0出发求出用邻接矩阵GA表//示的图的最小生成树,最小生成树的边集存于数组CT中voidPrim(RCWCT[],intn);//检查输入的边序号是否越界,若越界则重输voidCheck(intn,int&i,int&j);};图实现文件Graph.cpp//20052381

7、杨松Graph.cpp#include"Graph.h"//构造函数,初始化图的邻接矩阵与边集数组adjMList::adjMList(RCWGE[],intn,inte){inti,j;for(i=0;i

8、<<"{";for(i=0;i<=e-2;i++)if(ge[i].weight>0){k++;cout<<'('<