1 /*MST.cpp 带权无向图的最小生成树的构造*/  2 #include 
     
        3 #include 
      
         4 #define MAXV 100  5 #define MaxSize 1000  6 #define INF 32767  7 typedef int InfoType;  8   9 typedef struct  10 { 11     int no;                        /*顶点编号*/ 12     InfoType info;                /*顶点其他信息*/ 13 } VertexType;                    /*顶点类型*/ 14  15 typedef struct                  /*图的定义*/ 16 { 17     int edges[MAXV][MAXV];         /*邻接矩阵*/ 18     int n, e;                   /*顶点数，弧数*/ 19     VertexType vexs[MAXV];        /*存放顶点信息*/ 20 } MGraph;                        /*图的邻接矩阵类型*/ 21  22 void Prim(MGraph g, int v)      /*普里姆算法*/ 23 { 24     int lowcost[MAXV];            /*顶点i是否在U中*/ 25     int min; 26     int closest[MAXV], i, j, k; 27      28     for (i = 0; i < g.n; i++)              /*给lowcost[]和closest[]置初值*/ 29     {     30         lowcost[i] = g.edges[v][i]; 31         closest[i] = v; 32     } 33      34     for (i = 1; i < g.n; i++)              /*找出n-1个顶点*/ 35     { 36         min = INF; 37          38         for (j = 0; j < g.n; j++)       /*在(V-U)中找出离U最近的顶点k*/ 39         { 40             if (lowcost[j] != 0 && lowcost[j] < min)  41             { 42                 min = lowcost[j]; 43                 k = j;            /*k记录最近顶点的编号*/ 44             } 45         } 46          47         printf("边(%d,%d)权为：%d\n", closest[k], k, min); 48         lowcost[k] = 0;             /*标记k已经加入U*/ 49          50         for (j = 0; j < g.n; j++)       /*修改数组lowcost和closest*/ 51         { 52             if (g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j]) 53             { 54                 lowcost[j] = g.edges[k][j]; 55                 closest[j] = k;  56             } 57         } 58     } 59 } 60  61 typedef struct  62 {     63     int u;                        /*边的起始顶点*/ 64     int v;                        /*边的终止顶点*/ 65     int w;                        /*边的权值*/ 66 } Edge;                         /*带权边的存储结构*/ 67  68 int cmp(const void *a,const void *b)  69 {  70     return (*(Edge *)a).w > (*(Edge *)b).w ? 1 : -1;  71 } 72  73 void Kruskal(MGraph g)              /*克鲁斯卡尔算法*/ 74 { 75     int i, j, u1, v1, sn1, sn2, k; 76     int vset[MAXV]; 77     Edge E[MaxSize];                /*存放所有边*/ 78      79     k = 0;                            /*E数组的下标从0开始计*/ 80     for (i = 0; i < g.n; i++)        /*由g产生的边集E*/ 81     { 82         for (j = 0; j < g.n; j++) 83         { 84             if (g.edges[i][j] != 0 && g.edges[i][j] != INF) 85             { 86                 E[k].u = i; 87                 E[k].v = j; 88                 E[k].w = g.edges[i][j]; 89                 k++; 90             } 91         } 92     } 93      94     qsort(E, k, sizeof(E[0]), cmp);     /*采用快速排序对E数组按权值递增排序*/ 95  96     for (i = 0; i < g.n; i++) vset[i] = i;            /*初始化辅助数组*/ 97          98     k = 1;                             /*k表示当前构造生成树的第几条边,初值为1*/ 99     j = 0;                             /*E中边的下标,初值为0*/100     while (k < g.n)                   /*生成的边数小于n时循环*/101     {    102         u1 = E[j].u;103         v1 = E[j].v;                /*取一条边的头尾顶点*/104         sn1 = vset[u1];105         sn2 = vset[v1];             /*分别得到两个顶点所属的集合编号*/106         107         if (sn1 != sn2)               /*两顶点属于不同的集合,该边是最小生成树的一条边*/108         {    109             printf("边(%d,%d)的权为：%d\n", u1, v1, E[j].w);110             k++;                    /*生成边数增1*/111             for (i = 0; i < g.n; i++)   /*两个集合统一编号*/112                 if (vset[i] == sn2)      /*集合编号为sn2的改为sn1*/113                     vset[i] = sn1;114         }115         116         j++;                           /*扫描下一条边*/117     }118 }119 120 typedef struct node121 {    122     int rank;        /*结点对应秩*/123     int parent;        /*结点对应双亲下标*/124 } UFSTree;            /*并查集树结点类型*/125 126 void MAKE_SET(UFSTree t[], int n)    /*初始化并查集树*/127 { 128     int i;129     130     for (i = 0; i < n; i++)        /*顶点编号从0到n-1*/131     {132         t[i].rank = 0;        /*秩初始化为0*/133         t[i].parent = i;        /*双亲初始化指向自已*/134     }135 }136 137 int FIND_SET(UFSTree t[], int x)    /*在x所在子树中查找集合编号*/138 {139     if (x != t[x].parent)                /*双亲不是自已*/140         return FIND_SET(t, t[x].parent);/*递归在双亲中找x*/141     else142         return x;                        /*双亲是自已,返回x*/143 }144 145 void UNION(UFSTree t[], int x, int y)    /*将x和y所在的子树合并*/146 { 147     x = FIND_SET(t, x);148     y = FIND_SET(t, y);149     if (t[x].rank > t[y].rank)            /*y结点的秩小于x结点的秩*/150         t[y].parent = x;                /*将y连到x结点上,x作为y的孩子结点*/151     else                                /*y结点的秩大于等于x结点的秩*/152     { 153         t[x].parent = y;                /*将x连到y结点上,y作为x的孩子结点*/154         if (t[x].rank == t[y].rank)        /*x和y结点的秩相同*/155             t[y].rank++;                /*y结点的秩增1*/156     }157 }158 159 void Kruskal1(MGraph g)          /*改进的克鲁斯卡尔算法*/160 {161     int i, j, k, u1, v1, sn1, sn2;162     UFSTree t[MaxSize];163     Edge E[MaxSize];164     165     k = 1;                    /*e数组的下标从1开始计*/166     for (i = 0; i < g.n; i++)        /*由g产生的边集e*/167     {168         for (j = 0; j < g.n; j++)169         {170             if (g.edges[i][j] != 0 && g.edges[i][j] != INF)171             {172                 E[k].u = i;173                 E[k].v = j;174                 E[k].w = g.edges[i][j];175                 k++;176             }177         }178     }179     180     qsort(E, k, sizeof(E[0]), cmp);     /*采用快速排序对E数组按权值递增排序*/181     MAKE_SET(t, g.n);        /*初始化并查集树t*/182     k = 1;                   /*k表示当前构造生成树的第几条边,初值为1*/183     j = 1;                   /*E中边的下标,初值为1*/184     185     while (k < g.n)           /*生成的边数小于n时循环*/186     {    187         u1 = E[j].u;188         v1 = E[j].v;        /*取一条边的头尾顶点编号u1和v2*/189         sn1 = FIND_SET(t, u1);190         sn2 = FIND_SET(t, v1);  /*分别得到两个顶点所属的集合编号*/191         192         if (sn1 != sn2)         /*两顶点属于不同的集合,该边是最小生成树的一条边*/193         {    194             printf("边(%d,%d)的权为：%d\n", u1, v1, E[j].w);195             k++;                /*生成边数增1*/196             UNION(t, u1, v1);    /*将u1和v1两个顶点合并*/197         }198         199         j++;                   /*扫描下一条边*/200     }201 }202 203 int main()                  /*主函数*/204 { 205     int i, j, n;206     MGraph g;207     printf("请输入带权无向图的顶点个数：");/*6*/208     209     while (scanf("%d", &n) != EOF) 210     {211         printf("请输入带权无向图的邻接矩阵：\n");212         /*213         0 5 8 7 32767 3214         5 0 4 32767 32767 32767215         8 4 0 5 32767 9216         7 32767 5 0 5 6217         32767 32767 32767 5 0 1218         3 32767 9 6 1 0219         */220         for (i = 0; i < n; i++)221         {222             for (j = 0; j < n; j++)223             {224                 scanf("%d", &g.edges[i][j]);225             }226         }227         228         g.n = n;229         printf("\n采用普里姆算法得到的最小生成树为：\n");Prim(g, 0);230         printf("\n采用克鲁斯卡尔算法得到的最小生成树为：\n");Kruskal(g);231         printf("\n采用改进的克鲁斯卡尔算法得到的最小生成树为：\n");Kruskal1(g);232         printf("\n请输入带权无向图的顶点个数：");233     }234     235     return 0;236 }