#include <stdio.h>

#define inf 9999

#define max 40

prim(int g[][max],int n)

{int lowcost[max],closest[max];

int i,j,k,min;

for(i=2;i<=n;i++) //n个顶点，n-1条边

{lowcost[i]=g[1][i]; //初始化

closest[i]=1; //顶点未加入到最小生成树中

}

lowcost[1]=0; //标志顶点1加入U集合

for(i=2;i<=n;i++) //形成n-1条边的生成树

{min=inf;

k=0;

for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边

if((lowcost[j]<min)&&(lowcost[j]!=0))

{min=lowcost[j];

k=j;

}

printf("(%d,%d)%d\t",closest[k],k,min);

lowcost[k]=0; //顶点k加入U

for(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值

if(g[k][j]<lowcost[j])

{lowcost[j]=g[k][j];

closest[j]=k;

}

printf("\n");

}

}





int adjg(int g[][max]) //建立无向图

{int n,e,i,j,k,v1,v2,weight;

printf("输入顶点个数，边的条数：");

scanf("%d,%d",&n,&e);

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

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

g[i][j]=inf; //初始化矩阵，全部元素设为无穷大

for(k=1;k<=e;k++)

{printf("输入第%d条边的起点，终点，权值:",k);

scanf("%d,%d,%d",&v1,&v2,&weight);

g[v1][v2]=weight;

g[v2][v1]=weight;

}

return(n);

}





void prg(int g[][max],int n) //输出无向图的邻接矩阵

{int i,j;

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

printf("%d\t",i);

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

{printf("\n%d\t",i);

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

printf((g[i][j]==inf)?"\t":"%d\t",g[i][j]);

}

printf("\n");

}





main()

{int g[max][max],n;

n=adjg(g);

printf("输入无向图的邻接矩阵:\n");

prg(g,n);

printf("最小生成树的构造:\n");

prim(g,n);

}

  回复  更多评论