プリムアルゴリズム最小生成ツリー
2004 ワード
#include "stdio.h"
#include "stdlib.h"
#define MAXINT 32767
#define MAX 100
/* , */
/*
test data: 6 0 1 1 0 2 33 0 3 43 0 4 5 0 5 32 1 2 3 1 3 4 1 4 5 1 5 76 2 3 2 2 4 5 2 5 6 3 4 5 3 5 665 4 5 4 -1 -1 -1
result:
please input node num:
(V0 ,V1)(V1 ,V2)(V2 ,V3)(V0 ,V4)(V4 ,V5)the sum is 15
*/
//
void read(int a[][MAX],int *v)
{
int n,i,j,w;
printf("please input node num:
");
scanf("%d",&n);
if(n>MAX)
{
printf("input node value not > %d",MAX);
return;
}
*v=n;
// a
for(i=0;i<n;i++)
for(j=0;j<n;j++)a[i][j]=MAXINT;
do
{
scanf("%d%d%d",&i,&j,&w);
if(i==-1||j==-1||w==-1)break;
a[i][j]=w;
}while(9);
}
void plmMST(int a[][MAX],int n)
{
int c,i,j,min_w,min_i,min_j,sum=0;
// 0
a[0][0]=-1;
for(c=0;c<n-1;c++)
{
min_w = MAXINT;
min_i = -1;
min_j = -1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
// , i ( )
if(i!=j&&(a[i][i]==-1&&a[j][j]!=-1||a[i][i]!=-1&&a[j][j]==-1)&&a[i][j]<min_w)
{
min_w=a[i][j];
min_i=i;
min_j=j;
}
}
}
// ,
if(min_i!=-1)
{
printf("(V%-2d,V%d)",min_i,min_j);
//a[min_i][min_j]=MAXINT;?
a[min_i][min_i]=a[min_j][min_j]=-1;
sum+=min_w;
}
else
{
printf("
");
exit(-2);
}
}
printf("the sum is %d
",sum);
}
void main()
{
int a[MAX][MAX],vnum;
read(a,&vnum);
plmMST(a,vnum);
}