最小生成樹演算法深度解析：Prim 與 Kruskal 完整實作與複雜度比較

基本定義

• 生成樹：包含連通圖所有 n 個頂點，且有 n-1 條邊的子圖
• 最小生成樹 (MST)：帶權無向連通圖中，權值總和最小的生成樹
• 一個圖可有多棵生成樹，但 MST 權值總和唯一（邊權值不同時）

Prim 演算法 (普利姆)

適用稠密圖，從頂點出發貪婪擴展。

核心邏輯

1. 初始化：U = {V0}，TE = ∅
2. 重複 n-1 次：
   • 在所有 u∈U, v∈V-U 的邊中，選權值最小的邊 (u0, v0)
   • 將邊加入 TE，將 v0 加入 U
3. U = V 時結束，TE 即為 MST

程式碼實作 (鄰接矩陣)

#define MAXVEX 100
#define INFINITY 65535

void MiniSpanTree_Prim(MGraph G) {
    int min, i, j, k;
    int adjvex[MAXVEX];   // 最小邊的另一端頂點
    int lowcost[MAXVEX];  // 最小邊權值

    // 初始化：從 V0 開始
    lowcost[0] = 0;
    adjvex[0] = 0;
    for (i = 1; i < G.numVertexes; i++) {
        lowcost[i] = G.arc[0][i];
        adjvex[i] = 0;
    }

    for (i = 1; i < G.numVertexes; i++) {
        min = INFINITY;
        // 尋找最小權值邊
        for (j = 1; j < G.numVertexes; j++)
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }

        printf("邊 (%d, %d) 權值: %d\n", adjvex[k], k, min);
        lowcost[k] = 0;  // 標記已加入 U

        // 更新 lowcost
        for (j = 1; j < G.numVertexes; j++)
            if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
    }
}

Kruskal 演算法 (克魯斯卡爾)

適用稀疏圖，從邊出發貪婪選擇。

核心邏輯

1. 將所有邊按權值遞增排序
2. 初始化：每個頂點自成一棵樹 (森林)
3. 依序檢查邊：若邊兩端點屬不同樹，合併樹並選入該邊；否則捨棄(會成環)
4. 直到森林只剩一棵樹 (n-1 條邊)

關鍵資料結構：並查集

int parent[MAXVEX];

int Find(int x) {
    while (parent[x] >= 0) x = parent[x];
    return x;
}

void Union(int x, int y) {
    int rx = Find(x), ry = Find(y);
    if (rx != ry) parent[rx] = ry;
}

程式碼實作

typedef struct {
    int begin, end;
    int weight;
} Edge;

void MiniSpanTree_Kruskal(MGraph G) {
    Edge edges[MAXVEX * MAXVEX];
    int edgeCount = 0;

    // 收集所有邊 (無向圖只取上三角)
    for (int i = 0; i < G.numVertexes; i++)
        for (int j = i + 1; j < G.numVertexes; j++)
            if (G.arc[i][j] != INFINITY) {
                edges[edgeCount++] = {i, j, G.arc[i][j]};
            }

    // 排序 (可用 qsort)
    qsort(edges, edgeCount, sizeof(Edge), cmpWeight);

    // 初始化並查集
    for (int i = 0; i < G.numVertexes; i++) parent[i] = -1;

    int selected = 0;
    for (int i = 0; i < edgeCount && selected < G.numVertexes - 1; i++) {
        int u = Find(edges[i].begin);
        int v = Find(edges[i].end);
        if (u != v) {
            Union(u, v);
            printf("選擇邊 (%d, %d) 權值: %d\n", edges[i].begin, edges[i].end, edges[i].weight);
            selected++;
        }
    }
}

演算法比較總結

經典例題演示

參考文章中的圖示範例：Kruskal 依序選擇權值 5, 5, 6, 7, 7, 9 的邊，跳過會成環的 8, 8, 8，最終構成 MST。完美展現貪婪策略「局部最優 → 整體最優」的特性。