Prim(普里姆)算法求最小生成树

#include<stdio.h>

#define MaxVertexNum 20

#define INF 32767

typedef struct

{

       int vexs[MaxVertexNum];

       int AdjMatrix[MaxVertexNum][MaxVertexNum];

       int vexnum,arcnum;

}MGraph;

typedef struct

{

       int begin,end;

       int cost;

}TreeEdge;

void CreatMGraph1(MGraph &G)

{

       int i,j,k,x;

       printf("请输入顶点数和边数（输入格式为：顶点数 边数）:\n");

       scanf("%d %d",&(G.vexnum),&(G.arcnum));

       for(i=0;i<G.vexnum;i++)

                for(j=0;j<G.vexnum;j++)

                          G.AdjMatrix[i][j]=INF;

       printf("输入%d条边,格式：行下标 列下标边上的权值<CR>\n",G.arcnum);

       for(k=0;k<G.arcnum;k++)

       {

                scanf("%d %d %d",&i,&j,&x);G.AdjMatrix[i][j]=x;

                G.AdjMatrix[j][i]=G.AdjMatrix[i][j];

       }

}

void Prim(MGraph &G)

{

       int n=G.vexnum;

       int lowerCost[MaxVertexNum],mincost=0,closeVertex[MaxVertexNum];

       TreeEdge close[MaxVertexNum];

       int i,j,k,sum=0;

       for(i=1;i<n;i++)

       {lowerCost[i]=G.AdjMatrix[0][i];closeVertex[i]=0;}

       lowerCost[0]=0;

       closeVertex[0]=0;

       for(i=1;i<n;i++)

       {

                mincost=INF;

                j=1;k=1;

                while(j<n)

                {

                          if(lowerCost[j]!=0&&lowerCost[j]<mincost)

                          {mincost=lowerCost[j];k=j;}

                          j++;

                }

                close[i-1].begin=closeVertex[k];close[i-1].end=k;close[i-1].cost=mincost;

                sum=sum+mincost;

                lowerCost[k]=0;

                for(j=1;j<n;j++)

                          if(G.AdjMatrix[k][j]<lowerCost[j])

                          {lowerCost[j]=G.AdjMatrix[k][j];closeVertex[j]=k;}

       }

       printf("最小生成树如下所示：\n始点  终点  权值\n");

       for(i=0;i<n-1;i++)

       {printf("%d %d %d\n",close[i].begin,close[i].end,close[i].cost);}

       printf("最小生成树的总权和为%d\n",sum);

}

main()

{

       MGraph G;

       CreatMGraph1(G);

       Prim(G);

}

运行结果：