《最小生成树算法实验报告.doc》由会员分享，可在线阅读，更多相关《最小生成树算法实验报告.doc（6页珍藏版）》请在三一办公上搜索。
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的真子集，就做如下的贪心选择：选取满足条件iU,jV-U,且使c(i,j)达到最小
2、的边(i,j),并将顶点j添加到U中。这个过程一致进行到U=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 时间复杂度Prim算法的Pascal语言描述如下：Procedure PRIM(c:array1.n,1.n of real);Varlowcost:array1.n of real;closest:array1.n of integer;i,j,k,min,integer;begin(1) for i:=2 to n do(2) begin初始化，此时U只含有顶点1(3) lowcosti:=c1,i;(4) Closesti:=1;(5) end;(6) for i
3、:=2 to n do(7) begin 寻找顶点分别在V-U与U中边权最小的边(8) min:=lowcosti;(9) j:=i;(10) For k:=2 to n do(11) If lowcostkmin then(12) Begin(13) Min:=lowcostk;(14) j:=k;(15) End;(16) print(j,closestj);输出找到的边(17) Lowcostj:=;将j添加到U(18) For k:=2 to n do 调整lowcost和closest(19) if(cj,klowcostk)and(lowcostk )then(20) Begin(
4、21) Lowcostk:=cj,k;(22) Closestk:=j;(23) End(24) End(25) End;PRIM上述过程中第(6)(24)行的for循环要执行n-1次，每次执行时，第(10)(15)行和第(18)(23)行的for循环都要O(n)时间，所以Prim算法所需的计算时间为O(n)。 实验源代码图定义头文件Graph.h：const int MaxV=10;/最多顶点数const int MaxValue=99;/最大权值/定义边集数组中的元素类型struct RCWint row,col; int weight; class adjMListprivate: in
5、t numE;/当前边数 int GAMaxVMaxV;/定义邻接矩阵public: /构造函数,初始化图的邻接矩阵与边集数组 adjMList(RCW GE,int n,int e); /建立无向带权图的邻接矩阵 void CreateMatrix(int n,int &e,RCW r); /输出边集数组中的每条边 void OutputEdgeSet(RCW ge,int e); /根据图的邻接矩阵生成图的边集数组 void ChangeEdgeSet(RCW GE,int n,int e); /按升序排列图的边集数组 void SortEdgeSet(RCW GE,int e); /利用
6、普里姆算法从顶点v0出发求出用邻接矩阵GA表 /示的图的最小生成树,最小生成树的边集存于数组CT中 void Prim(RCW CT,int n); /检查输入的边序号是否越界,若越界则重输 void Check(int n, int& i, int& j);图实现文件Graph.cpp/20052381 杨松 Graph.cpp#includeGraph.h/构造函数,初始化图的邻接矩阵与边集数组adjMList:adjMList(RCW GE,int n,int e)int i,j; for(i=0; in; i+) for(j=0; jn; j+) if(i=j) GAij=0; els
7、e GAij=MaxValue; for(i=0;ie;i+) GEi.weight=0; numE=0;/输出边集数组中的每条边void adjMList:OutputEdgeSet(RCW ge,int e)int i,k=0; cout; for(i=0; i0)k+; cout(gei.row,gei.col; cout,gei.weight) ; if(k%5=0) cout0&gei.weight0) cout(gee-1.row,gee-1.col; cout,gee-1.weight); coutendl;/建立无向带权图的邻接矩阵void adjMList:CreateMat
8、rix(int n,int &e,RCW r)int i,j,k=0,w; cout依次输入无向带权图的每条边的起点和终点endl; cout序号及权值!直到输入权值为0的边为止!ijw; Check(n,i,j); if(k=e-1) break; GAij=GAji=w;k+; while(1); numE=e=k; cout邻接矩阵:n; for(i=0;in;i+) for(j=0;jn;j+) coutsetw(4)GAij; coutendl;/检查输入的边序号是否越界,若越界则重输void adjMList:Check(int n, int& i, int& j)while(1)
9、 if(i=n |j=n) coutij;/根据图的邻接矩阵生成图的边集数组void adjMList:ChangeEdgeSet(RCW GE,int n,int e)/假定只考虑无向图的情况 int i,j,k=0; for(i=0; in; i+) for(j=i+1; jn; j+) if(GAij!=0 & GAij!=MaxValue) if(k=e) cout数组GE下标越界!n; exit(1); GEk.row=i; GEk.col=j; GEk.weight=GAij; k+; /按升序排列图的边集数组void adjMList:SortEdgeSet(RCW GE,int
10、 e)int i,j; RCW x; for(i=1; i=0; j-) if(x.weightGEj.weight) GEj+1=GEj; else break; GEj+1=x; /利用普里姆算法从顶点v0出发求出用邻接矩阵GA表示/的图的最小生成树,最小生成树的边集存于数组CT中void adjMList:Prim(RCW CT,int n)int i,j, k, min, t, m, w; /给CT赋初值，对应为v0依次到其余各顶点的边 for(i=0; in-1; i+) CTi.row=0; CTi.col=i+1; CTi.weight=GA0i+1; /进行n-1次循环，每次求
11、出最小生成树中的第k条边 for(k=1; kn; k+) /从CTk-1CTn-2中查找最短边CTm min=MaxValue; m=k-1; for(j=k-1; jn-1; j+) if(CTj.weightmin) min=CTj.weight; m=j; /把最短边对调到第k-1下标位置 RCW temp=CTk-1; CTk-1=CTm; CTm=temp; /把新并入最小生成树T中的顶点序号赋给j j=CTk-1.col; /修改有关边，使T中到T外的每一个顶点各保持 /一条到目前为止最短的边 for(i=k; in-1; i+) t=CTi.col; w=GAjt; if(wC
12、Ti.weight) CTi.weight=w; CTi.row=j;主程序文件 Test.cpp：/图的相关运算的测试graph2M.cpp#include#include#include#include Graph.cppvoid main() RCW rcw20=0,1,50,1,0,50,0,2,60,2,0,60, 1,3,65,3,1,65,1,4,40,4,1,40,2,3,52, 3,2,52,2,6,45,6,2,45,3,4,50,4,3,50, 3,5,30,5,3,30,3,6,42,6,3,42,4,5,70,5,4,70; int n,k;/定义图的点数及边数等 c
13、outn; coutk; static RCW AE30,BE30;/定义边集数组 adjMList A(AE,n,k); A.CreateMatrix(n,k,rcw); cout输出边集数组中的每条边:n; A.ChangeEdgeSet(AE,n,k); A.OutputEdgeSet(AE,k); cout输出按升序排列的图的边集数组:n; A.SortEdgeSet(AE,k); A.OutputEdgeSet(AE,k); A.Prim(BE,n); cout输出最小生成树的边集数组:n; A.OutputEdgeSet(BE,k); cin.get();cin.get(); 实验数据在主程序中直接构造图的边表如下，0,1,50,1,0,50,0,2,60,2,0,60, 1,3,65,3,1,65,1,4,40,4,1,40,2,3,52, 3,2,52,2,6,45,6,2,45,3,4,50,4,3,50, 3,5,30,5,3,30,3,6,42,6,3,42,4,5,70,5,4,70共7个顶点，10条边 实验结果
