プリムアルゴリズム最小生成ツリー



#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); }