• 克鲁斯卡尔算法

    克鲁斯卡尔算法

    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. }