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;

      intlowerCost[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);

}

运行结果：