ch6_3.c

清华出版社出版

#include <stdio.h>
#define M 10
#define MAX 100
void minispantree_PRIM(int ad[][M],int n)
{  int i,j,k,p,q,wm;
   q=p=n-1;
   ad[q][q]=1;
   for(k=0;k<(n-1);k++)
   {  wm=MAX;
      for(i=0;i<n;i++)
	 if(ad[i][i]==1)
	    for(j=0;j<n;j++)
	       if((ad[j][j]==0)&&(ad[i][j]<wm))
	       {   wm=ad[i][j];
		   p=i;
		   q=j;
	       }
      ad[q][q]=1;
      printf("%d %d %d\n",p+1,q+1,ad[p][q]);
      if(p>q)  ad[p][q]=-ad[p][q];
      else     ad[q][p]=-ad[q][p];
   }
}

void main()
{   int n=6,i,j;
    static int ad[][M]={{0  ,6  ,1,5  ,MAX,MAX},
			{6  ,0  ,5,MAX,3  ,MAX},
			{1  ,5  ,0,5  ,6  ,4},
			{5  ,MAX,5,0  ,MAX,2},
			{MAX,3  ,6,MAX,0  ,6},
			{MAX,MAX,4,2  ,6  ,0}};
    minispantree_PRIM(ad,n);
    for(i=0;i<n;i++)
    {  for(j=0;j<n;j++)
	 printf("%-6d",ad[i][j]);
       printf("\n");
    }
}