prim算法生成最小生成树(c++).

#include<iostream> using namespace std; const int maxsize=20; class algraph { public: algraph(char a[],int n,int e); void prim(); private: char vertex[maxsize]; //存放顶点的数组 int arc[maxsize][maxsize]; int vertexnum; int arcnum; }; void main() { int n,e; char a[10]={'0' ,'1', '2' ,'3' ,'4' ,'5', '6' ,'7', '8' ,'9'}; cout<<"输入顶点数:"; cin>>n; cout<<"输入边数 :"; cin>>e; algraph A(a,n,e); A.prim(); cout<<"\n"; } algraph::algraph(char a[],int n,int e) { vertexnum=n; arcnum=e; int info[20]={34,46,19,12,17,25,38,25,26,15,13,12}; //边所对应的权值 for(int i=0;i<vertexnum;i++) { vertex[i]=a[i]; } for(int k=0;k<vertexnum;k++) //初始化邻接矩阵 { for(int j=0;j<arcnum;j++) { arc[k][j]=50; } } for(int m=0;m<arcnum;m++) { int i,j; cout<<"输入便的两个顶点:"; cin>>i>>j; arc[i][j]=info[m]; arc[j][i]=info[m]; } } void algraph::prim() // 用prim算法生成最小生成树 { int lowcost[maxsize]; //未加入点与已加入个点之间最小权值 char adjver[maxsize]; //表示依附于该边的已加入的点 for(int i=1;i<vertexnum;i++) //如：adjver[i]=k,表示该边依附的两个位置是i,k，k为已加入的点 { lowcost[i]=arc[0][i]; adjver[i]=vertex[0]; } lowcost[0]=0; for(int l=1;l<vertexnum;l++) { int k=1; //用来存放最小权值对应点的位置 for(int g=1;g<vertexnum;g++) //每次从剩下的顶点中找到与已加入顶点权值最小那个点 { if(lowcost[k]==0) //跳过第一个结点 k++; else if(lowcost[g]<lowcost[k] && lowcost[g]!=0) k=g; } cout<<"("<<adjver[k]<<vertex[k]<<")"<<" "; //输出该边 lowcost[k]=0; //将该点加入最小生成树中 for(int j=1;j<vertexnum;j++) { if(lowcost[j]>arc[k][j]) //修改lowcost数值 { lowcost[j]=arc[k][j]; adjver[j]=vertex[k]; } } } }