kruskal.c

来自「最小生成树：一个单位内的10个办公点通过局域网连接」· C语言 代码 · 共 56 行

#include<stdio.h>
#define n 10
int g[9][9],boo[9],a,b,t=0;
/* 获取权 */
 int init()
{
 int i,j;
 printf("请按0---1,0---2,0---3,0---4 .....0---9");
 printf("\n");
 printf("    1---2,1---3,1---4 ..... 1---9");
 printf("\n");
 printf("    2---3,2---4 ..... 2---9");
 printf("\n");
 printf("    .....");
 printf("\n");
 printf("的顺序输入各点之间权");
 printf("\n");
 for(i=0;i<n;i++)
 for(j=i+1;j<n;j++)
 scanf("%d",&g[i][j]);
 for(i=0;i<n;i++)
 boo[i]=0;
 return 0;
}
/* 选取最小权 */
 int select()
{
 int i,j;
 t=10000;
 for(i=0;i<n;i++)
 if(boo[i])
 for(j=0;j<n;j++)
 if(!boo[j]&&i<j&&g[i][j]<t&&g[i][j]!=0)
 {
   a=i;b=j;t=g[i][j];
 }
 return 0;
}

int main()
{
 long i,j=0;
 init();
 boo[0]=1;
 for(i=1;i<n;i++)
 {
   select();
   printf("%d====%d\n",a,b);
   j+=t;
   boo[b]=1;
 }
 printf("%d\n",j);
 printf("\n\n\n\n");
 init();
 return 0;
}