- #include <iostream.h>
- #define MaxVertexNum 10
- #define MAXCOST 1000
- typedef char VertexType;
- typedef struct
- { VertexType vexs[MaxVertexNum]; //顶点信息
- int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵
- int n,e; //顶点和边数
- }MGraph;
- void CreateMGraph(MGraph &G); //创建邻接矩阵存储图
- void Prim(MGraph *G,int closevex[ ]); //Prim计算最小生成树
- void main ( )
- {
- MGraph G;
- int closevex[MaxVertexNum];
- CreateMGraph(G);
- Prim(&G,closevex);
- }
- void CreateMGraph(MGraph &G)
- {
- /*int i, j, k;
- cout<<"请输入顶点数和边数"<<endl;
- cin>>G.n>>G.e;
- cout<<"请输入顶点信息"<<endl;
- for (i=0;i<G.n;i++) cin>>G.vexs[i];
- for (i=0;i<G.n;i++)
- for (j=0;j<G.n;j++) G.edges[i][j]=0;
- cout<<"请输入每条边(对应的顶点序号)"<<endl;
- for (k=0;k<G.e;k++)
- { cin>>i>>j;
- G.edges[i][j]=1; G.edges[j][i]=1;}*/
- int i, j;
- G.n=7; G.e=10;
- for (i=0;i<G.n;i++)
- G.vexs[i]='A'+i;
- for (i=0;i<G.n;i++)
- {
- for ( j=0;j<G.n;j++)
- G.edges[i][j]=0;
- }
- //0 1 2 3 4 5 6 7
- //A B C D E F G H
- G.edges[0][1]=50; G.edges[1][0]=50; //(A,B)50
- G.edges[0][2]=60; G.edges[2][0]=60; //(A,C)60
- G.edges[1][3]=65; G.edges[3][1]=65; //(B,D)65
- G.edges[1][4]=40; G.edges[4][1]=40; //(B,E)40
- G.edges[2][3]=52; G.edges[3][2]=52; //(C,D)52
- G.edges[2][6]=45; G.edges[6][2]=45; //(C,G)45
- G.edges[3][5]=30; G.edges[5][3]=30; //(D,F)30
- G.edges[4][5]=70; G.edges[5][4]=70; //(E,F)70
- G.edges[3][6]=42; G.edges[6][3]=42; //(D,G)42
- G.edges[3][4]=50; G.edges[4][3]=50; //(D,E)50
- }
- void Prim(MGraph *G,int closevex[ ])
- {
- int lowcost[MaxVertexNum],mincost;
- int i, j,k;
- for (i=1;i<G->n;i++)
- {
- lowcost[i]=G->edges[0][i];
- closevex[i]=0;
- }
- lowcost[0]=0;
- closevex[0]=0;
- for (i=1;i<G->n;i++)
- {
- mincost=MAXCOST;
- j=1;k=1;
- while ( j<G->n)
- {
- if(lowcost[ j ]<mincost && lowcost[ j ]>0)
- {
- mincost=lowcost[j];
- k=j;
- }
- j++;
- }
- //cout<<"顶点的序号:"<<k+1<<"权值:"<<mincost<<endl;
- cout<<"("<<G->vexs[closevex[k]]<<","<<G->vexs[k]<<"):"<<mincost<<endl;
- lowcost[k]=-lowcost[k];
- for ( j=1; j<G->n; j++)
- {
- if (G->edges[k][j]>0 )
- {
- if(lowcost[j]>0 && G->edges[k][ j]<lowcost[j]||lowcost[j]==0 )
- {
- lowcost[j]=G->edges[k][j];
- closevex[j]=k;
- }
- }
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/160120148554.html
来源: http://www.codesnippet.cn/detail/160120148554.html