#include<stdio.h>
#include<malloc.h>
#define n0 100
int adjmatrix[n0+1][n0+1];
int n;
void create_adjmatrix()
/*创建邻接矩阵*/
{
int i,j,w;
printf("请输入顶点个数n:");
scanf("%d",&n);
/*初始化邻接矩阵*/
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
adjmatrix[i][j]=10000;
do
{
printf("请输入顶点i,j及它们的权w(用,隔开)**i,j,w:");
scanf("%d,%d,%d",&i,&j,&w);/*w为i,j所邻接的边的权值*/
if(i>n || j>n) break;/*只要输入的结点比n大即会退出*/
adjmatrix[i][j]=w;
adjmatrix[j][i]=w;
}while(1);
}
void ljjzprint()/*定义并输出邻接矩阵*/
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",adjmatrix[i][j]);
printf("\n");
}
}
/*Prim算法 */
void prim(int x)
{
int closeest[n0+1],mintotree[n0+1];/*closeest:与谁最近的点，mintotree:最小到树距离*/
int i,j,k,min;
int sum=0;
for(i=1;i<=n;i++)/*初始化*/
{
closeest[i]=x;
mintotree[i]=adjmatrix[x][i];
}
mintotree[x]=0;
for(i=2;i<=n;i++)
{
min=10000;/*无穷大*/
k=0;
for(j=1;j<=n;j++)/*在mintotree中找非0最小值*/
if(mintotree[j]!=0 && mintotree[j]<min)
{
min=mintotree[j];
k=j;
}
printf("<%d %d>* %d\t",i,closeest[i],min);
sum+=min;
mintotree[k]=0;
for(j=1;j<=n;j++)
if(mintotree[j]!=0 && mintotree[j]>adjmatrix[j][k])
{
closeest[j]=k;
mintotree[j]=adjmatrix[j][k];
}
printf("\n");
}
printf("最小生成树的代价==");
printf("%d",sum);
printf("\n");
printf("\n");
}
main()/*主函数--为程序做简单界面*/
{
char y='y';
create_adjmatrix();
printf("**********菜单**********\n");
printf("0---显示邻接矩阵\n");
printf("1---显示最小生成树prim\n");
printf("请选择你想要的结果*****\n");
while(y='y')
{int s;
char y='y';
scanf("%d",&s);
switch(s)
{
case 0:
printf("邻接矩阵如下:\n");
ljjzprint();
break;
case 1:
printf("prim算法及代价如下:\n");
prim(1);
break;
}
printf("继续吗y/n**(0/1):\n");
scanf("%c",&y);
if(y=='n')
break;
}
printf("*******************************\n");
printf("********制作者-ss-********\n");
printf("*******本人学号0606054335******\n");
printf("*******************************\n");
printf("\n");
}
