【报告】最小生成树算法实验报告
【关键字】报告
最小生成树算法
?问题描述
设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语言描述如下：
Procedure PRIM(c:array[1..n,1..n] of real);
Var
lowcost:array[1..n] of real;
closest:array[1..n] of integer;
i,j,k,min,integer;
begin
(1)for i:=2 to n do
(2)begin{初始化，此时U只含有顶点1}
(3)lowcost[i]:=c[1,i];
(4)Closest[i]:=1;
(5)end;
(6)for i:=2 to n do
(7)begin {寻找顶点分别在V-U与U中边权最小的边}
(8)min:=lowcost[i];
(9)j:=i;
(10)For k:=2 to n do
(11)If lowcost[k] (12)Begin (13)Min:=lowcost[k]; (14)j:=k; (15)End; (16)print(j,closest[j]);{输出找到的边} (17)Lowcost[j]:=∞;{将j添加到U} (18)For k:=2 to n do {调整lowcost和closest} (19)if(c[j,k] (20)Begin (21)Lowcost[k]:=c[j,k]; (22)Closest[k]:=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 RCW {int row,col; int weight; }; class adjMList { private: int numE;//当前边数 int GA[MaxV][MaxV];//定义邻接矩阵 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); //利用普里姆算法从顶点v0出发求出用邻接矩阵GA表 //示的图的最小生成树,最小生成树的边集存于数组CT中 void Prim(RCW CT[],int n); //检查输入的边序号是否越界,若越界则重输 void Check(int n, int& i, int& j); }; 图实现文件Graph.cpp // 杨松 Graph.cpp #include"Graph.h" //构造函数,初始化图的邻接矩阵与边集数组 adjMList::adjMList(RCW GE[],int n,int e) {int i,j; for(i=0; i for(j=0; j if(i==j) GA[i][j]=0; else GA[i][j]=MaxValue; for(i=0;i numE=0; } //输出边集数组中的每条边 void adjMList::OutputEdgeSet(RCW ge[],int e) {int i,k=0; cout<<"{"; for(i=0; i<=e-2; i++) if(ge[i].weight>0){k++; cout<<'('< cout<<','< if(k%5==0) cout< if(e>0&&ge[i].weight>0) { cout<<'('< cout<<','< cout<<'}'< } //建立无向带权图的邻接矩阵 void adjMList::CreateMatrix(int n,int &e,RCW r[]) {int i,j,k=0,w; cout<<"依次输入无向带权图的每条边的起点和终点"< //cin>>i>>j>>w; Check(n,i,j); if(k==e-1) break; GA[i][j]=GA[j][i]=w;k++; }while(1); numE=e=k; cout<<"邻接矩阵:\n"; for(i=0;i {for(j=0;j cout< cout< } //检查输入的边序号是否越界,若越界则重输 void adjMList::Check(int n, int& i, int& j) {while(1) { if(i<0 || i>=n ||j<0 || j>=n) cout<<"输入有误,请重输!"; else return; cin>>i>>j;} } //根据图的邻接矩阵生成图的边集数组 void adjMList::ChangeEdgeSet(RCW GE[],int n,int e) {//假定只考虑无向图的情况 int i,j,k=0; for(i=0; i for(j=i+1; j if(GA[i][j]!=0 && GA[i][j]!=MaxValue) {if(k==e) {cout<<"数组GE下标越界!\n"; exit(1);} GE[k].row=i; GE[k].col=j; GE[k].weight=GA[i][j]; k++; } } //按升序排列图的边集数组 void adjMList::SortEdgeSet(RCW GE[],int e) {int i,j; RCW x; for(i=1; i<=e-1; i++) {x=GE[i]; for(j=i-1; j>=0; j--) if(x.weight else break; GE[j+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; i {CT[i].row=0; CT[i].col=i+1; CT[i].weight=GA[0][i+1];} //进行n-1次循环，每次求出最小生成树中的第k条边 for(k=1; k {//从CT[k-1]~CT[n-2]中查找最短边CT[m] min=MaxValue; m=k-1; for(j=k-1; j if(CT[j].weight min=CT[j].weight; m=j;} //把最短边对调到第k-1下标位置 RCW temp=CT[k-1]; CT[k-1]=CT[m]; CT[m]=temp; //把新并入最小生成树T中的顶点序号赋给j j=CT[k-1].col; //修改有关边，使T中到T外的每一个顶点各保持 //一条到目前为止最短的边 for(i=k; i t=CT[i].col; w=GA[j][t]; if(w CT[i].weight=w; CT[i].row=j; }}}} 主程序文件 Test.cpp： //图的相关运算的测试graph2M.cpp #include #include #include #include "Graph.cpp" void main() { RCW rcw[20]={{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;//定义图的点数及边数等 cout<<"输入图的点数n=";cin>>n; cout<<"输入图的边数k=";cin>>k; static RCW AE[30],BE[30];//定义边集数组 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条边 ?实验结果 此文档是由网络收集并进行重新排版整理.word可编辑版本！