我们把构造连通网的最小代价生成树称为**最小生成树(Minimum Cost Spanning Tree)**。
　　　找连通网的最小生成树，有两种经典的算法，普里姆算法和克鲁斯卡尔算法。

  • 普利姆（Prim）算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
     1 // Prim算法生成最小生成树
     2 void MiniSpanTree_Prim(MGraph G) {
     3     int min, i, j, k;
     4     int adjvex[MAXVEX]; // 保存相关顶点下标
     5     int lowcost[MAXVEX]; // 保存相关顶点间边的权值
     6     lowcost[0] = 0; // 初始化第一个权值为0，即v₀加入生成树
     7                     // lowcost的值为0，在这里就是此下标的顶点已经加入生成树
     8     adjvex[0] = 0; // 初始化第一个顶点下标为0
     9     for (i = 1; i < G.numVerexes; i++) { // 循环除下标为0外的全部顶点
    10         lowcost[i] = G.arc[0][i]; // 将v₀顶点与之有边的权值存入数组
    11         adjvex[i] = 0; // 初始化都为v₀的下标
    12     }
    13     for (i = 1; i < G.numVertexes; i++) {
    14         min = INFINITY; // 初始化最小权值为∞，通常设置为不可能的大数字如32767、65535等
    15         j = 1;
    16         k = 0;
    17         while (j < G.numVertexes) { // 循环全部顶点
    18             if (lowcost[j]!=0 && lowcost[j]<min) { // 如果权值不为0且权值小于min
    19                 min = lowcost[j]; // 则让当前权值成为最小值
    20                 k = j; // 将当前最小值的下标存入k
    21             }
    22             j++;
    23         }
    24         printf("(%d,%d)", adjvex[k], k); // 打印当前顶点边种权值最小边
    25         lowcost[k] = 0; // 将当前顶点的权值设置为0，表示此顶点已经完成任务
    26         for (j = 1; j < G.numVertexes; j++) { // 循环所有顶点
    27             if (lowcost[j]!=0 && G.arc[k][j] < lowcost[j]) { // 若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
    28                 lowcost[j] = G.arc[k][j]; // 将较小权值存入lowcost
    29                 adjvex[j] = k; // 将下标为k的顶点存入adjvex
    30             }
    31         }
    32     }
    33 }

  • 克鲁斯卡尔（Kruskal）算法
    （我还没学）