kruskal.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/*********************************************/
/*      kruskal求解最小生成树算法            */
/*     文件名kruskal.c  函数名kruskal()      */
/*********************************************/
typedef struct edgedata  /*用于保存最小生成树的边类型定义*/
       { int beg,en;     /*beg,en是边顶点序号*/
         int length;     /*边的权值长*/
       }edge;

/*----kruskal算法构造最小生成树------*/

void kruskal(edge adjlist[],edge tree[],int cnvx[],int n)
  {  int v=0,j,k;
     for (j=0;j<n;j++)
                 cnvx[j]=j; /* 设置每一个顶点的连通分量 */

     for (k=0;k<n-1;k++)  /*树中其有n-1条边*/
       {
	  while (cnvx[adjlist[v].beg]==cnvx[adjlist[v].en] ) v++;
            /*找到属于两个连通分量权最小的边*/
	  tree[k]=adjlist[v];            /*将边V加入到生成树中*/
          for (j=0;j<n;j++)              /*两个连通分量合并为一个连通分量*/
             if (cnvx[j]==cnvx[adjlist[v].en])
                    cnvx[j]=cnvx[adjlist[v].beg];
          v++;
        }
     printf("最小生成树是：\n");
     for (j=0;j<n-1;j++)
	 printf("%3d%3d%6d\n",tree[j].beg,tree[j].en,tree[j].length);
   }

 void sort(edge adjlist[],int len)
 { /* 用冒泡排序法按边的权值大小进行升序排序 */
   edge x;
   int i,j,flag=1;
   for (i=1;i<len;i++)
     { flag=0;
       for (j=0;j<len-i;j++)
	  if (adjlist[j].length>adjlist[j+1].length)
              {x=adjlist[j];
               adjlist[j]=adjlist[j+1];
               adjlist[j+1]=x;
	       flag=1;
              }
       if (flag==0) return;
      }
 }
 void  main()
  {int n,e;
   edge  tree[20];    /*用于存放最小生成树的n-1条边,此处假设n<=20*/
   edge adjlist[200];
   int i,cnvx[20];    /*cnvx[]用于存放每个顶点所在的连通分量编号*/
   printf("Please input n and e:");
   scanf("%d%d",&n,&e);
   printf("请输入图中的边信息\n");
   for (i=0;i<e;i++)
     scanf("%d%d%d",&adjlist[i].beg,&adjlist[i].en,&adjlist[i].length);
   sort(adjlist,e);	   /*边排序*/
   kruskal( adjlist, tree,cnvx,n);
  }