#include<stdio.h>
#include<string.h>
#define maxn 21
#define inf 1000000
int n,m;
int edge[maxn][maxn];
int lowcost[maxn];
int nearvex[maxn];
void prim(int u0)
{
int sumweight=0;
int i,j;
for(i=1;i<=n;i++)//顶点是从1开始
{
lowcost[i]=edge[u0][i];
nearvex[i]=u0;
}
lowcost[u0]=0;
nearvex[u0]=-1;
for(i=1;i<n;i++)//将n-1个顶点加入到顶点集合T2
{
int min=inf;
int v=-1;
for(j=1;j<=n;j++)
{
if(nearvex[j]!=-1&&lowcost[j]<min)
{
min=lowcost[j];
v=j;
}
}
if(v!=-1)
{
printf("%d %d %d\n",nearvex[v],v,lowcost[v]);
nearvex[v]=-1;
sumweight+=lowcost[v];
for(j=1;j<=n;j++)
{
if(nearvex[j]!=-1&&edge[v][j]<lowcost[j])//j在T1集合中&&满足v到j的距离小于j到T2中顶点的最小值
{
lowcost[j]=edge[v][j];
nearvex[j]=v;
}
}
}
}
printf("sumweight of the mst is %d\n",sumweight);
}
int main()
{
int i,j;
int u,v,w;
scanf("%d%d",&n,&m);
memset(edge,0,sizeof(edge));
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
edge[u][v]=edge[v][u]=w;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)
edge[i][j]=0;
else if(edge[i][j]==0)
edge[i][j]=inf;
}
}
prim(1);//从顶点1中构造最小生成树
return 0;
}
prim 算法是基于顶点来实现最小生成树的，我们假设使用邻接矩阵来存储图的，在 prim 算法实现的过程中，我们需要知道以下两类信息
1.集合T1内各顶点到集合T2中个顶点的权值最小边的权值 //其中T2集合是表示这些集合中的点已经是最小生成树中的点了
2.集合T1内个顶点距离集合T2中哪个顶点的距离最小
为此，我们用两个数组来实现上面两类信息
lowcost[maxn]:用来实现1.
nearvex[maxn]:用来实现2.
实际上如果只是要计算最小生成树的最小代价是不需要使用nearvex[maxn]这个数组的，这个数组只是用来记录在构造最小生成树中的顶点的顺序。
prim算法的思想：
初始：lowcost[k]=edge[v0][k] , nearvex[k]=v0;其中v0指的是从哪点来构造最小生成树。
当lowcost[i]=-1时我们让它表示i顶点加入到了T2集合，
什么样的情况下我们将i结点加入到T2集合呢？
我们选择那些在T1集合中，距离T2集合中点最小的lowcost[k],将该点k加入到集合T2中，
加入后我们应该改变那些在T1集合中点到T2集合中的最小权值，如果edge[k][i]<lowcost[i]
则将lowcost[i]=edge[k][i];nearvex[i]=k;这就完成了一次操作，进行n-1次后，就能构成一个最小生成树