#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);
}
運作結果:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiYWan5ycuFmc091Zz9CXu9Wbt92Yvw1cldWYtl2LcVGb5R3c3c2bsJ2Lc52YuMnah5Waz5yZtl2cvw1LcpDc0RHaiojIsJye.gif)