克鲁斯卡尔算法

  1. #include <stdio.h>
  2. #define MAXVEX 100
  4. typedef struct 
  5. {    
  6.     int u;     /*边的起始顶点*/
  7.     int v;     /*边的终止顶点*/
  8.     int w;     /*边的权值*/
  9. } Edge;
  11. void Kruskal(Edge E[],int n,int e)
  12. {
  13.     int i,j,m1,m2,sn1,sn2,k;
  14.     int vset[MAXVEX];
  15.     for (i=0;i<n;i++) vset[i]=i;    /*初始化辅助数组*/
  16.     k=1;                             /*k表示构造最小生成树的第几条边,初值为1*/
  17.     j=0;                             /*E中边的下标,初值为0*/
  18.     while (k<n)                       /*生成的边数小于n时循环*/
  19.     {
  20.         m1=E[j].u;m2=E[j].v;        /*取一条边的头尾顶点*/
  21.         sn1=vset[m1];sn2=vset[m2];     /*分别得到两个顶点所属的集合编号*/
  22.         if (sn1!=sn2)                   /*两顶点属不同的集合,该边是最小生成树的边*/
  23.         {
  24.             printf("  边(%d,%d)权为:%d\n",m1,m2,E[j].w);
  25.             k++;                    /*生成边数增1*/
  26.             for (i=0;i<n;i++)          /*两个集合统一编号*/
  27.                 if (vset[i]==sn2)      /*集合编号为sn2的改为sn1*/
  28.                     vset[i]=sn1;
  29.         }
  30.         j++;                           /*扫描下一条边*/
  31.     }
  32. }
  34. void main()
  35. {
  36.     int n=7,e=10;
  37.     Edge E[]={
  38.         {3,5,30},{1,4,40},{3,6,42},
  39.         {2,6,45},{0,1,50},{3,4,50},
  40.         {2,3,52},{0,2,60},{1,3,65},
  41.         {4,5,70}};
  42.     printf("最小生成树:\n");Kruskal(E,n,e);
  43. }