mintree.c

来自「本源码可供数据结构的初学者借鉴」· C语言 代码 · 共 47 行

#include "stdio.h"
#define max  100
#define   n   8
typedef struct derect
       {  int vex,infro ;
       }sup;
void prim(char vex[n],int rel[n][n],int k)
{  sup  c[n];
   int min,i,j,p;
   for(i=0;i<n;i++)                            /*初始化指示c[]*/
          if(i!=k)
              {  c[i].infro=rel[k][i];
                 c[i].vex=1;
              }
   c[k].vex=0;    printf("%c ",vex[k]);            /*给s中第一个节点输出*/
   for(i=0;i<n-1;i++)                                 /*循环n次把节点都加入s中*/
     {   min=max;
         for(j=0;j<n;j++)
             if(c[j].vex!=0&&c[j].infro<min)          /*找出v中的最小值*/
                  {   min=c[j].infro;
                      p=j;
                  }
         c[p].vex=0;  printf("->(%d)->%c",min,vex[p]);   /*把最小值放在s中*/
         for(j=0;j<n;j++)                              /*更换v中的c[]中的值*/
               if(c[j].vex!=0&&rel[p][j]<c[j].infro)
                       c[j].infro=rel[p][j];

     }


}
main()
{  char vex[n]={'a','b','c','d','e','f','g','h'} ;
   int rel[n][n]={   {0,2,3,max,max,max,max,max},
                    {2,0,max,2,max,max,max,max},
                    {3,max,0,1,max,max,max,max},
                    {max,2,1,0,5,4,max,max},
                    {max,max,max,5,0,1,4,max},
                    {max,max,max,4,1,0,6,1},
                    {max,max,max,max,4,6,0,3},
                    {max,max,max,max,max,1,3,0}
               } ,k=0;

  prim(vex,rel,k);
  getch();
}