最小生成树 typedef char VerT; typedef char DataType; #include "AdjMWGraph.h" #include "Prim.h" #include "GraphLib.h"

void main(void) { AdjMWGraph g; char a[]={'A','B','C','D','E','F','G'}; RowColWeight rcw[]={{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=7,e=20; CreatGarph(g,a,n,rcw,e);//建立邻接矩阵的程序你自己加上去 Prim(g); } //Prim.h void Prim(AdjMWGraph &G) { int n=G.NumOfVertices(),minCost; int *lowCost=new int[n]; int i,j,k; for(i=0;i<n;i++) lowCost[i]=G.GetWeight(0,i); cout<<"顶点值="<<G.GetValue(0)<<endl; for(i=1;i<n;i++) { minCost=MaxWeight; j=1;k=1; while(j<n){ if(lowCost[j]<minCost&&lowCost[j]!=0) { minCost=lowCost[j]; k=j; } j++; } cout<<"顶点值="<<G.GetValue(k)<<'\t'<<"边的权值="<<minCost<<endl; lowCost[k]=0; for(j=1;j<n;j++){ if(G.GetWeight(k,j)<lowCost[j]) lowCost[j]=G.GetWeight(k,j); } } }