最小生成樹算法解析：暢通工程問題的經典應用

問題描述

「暢通工程」是典型的最小生成樹（Minimum Spanning Tree，MST）問題。給定 N 個村莊（節點）及其兩兩之間的距離（邊權），目標是用最短的總公路長度連通所有村莊，即尋找圖的最小生成樹。

輸入輸出格式

• 輸入：多組測試用例，每組第一行 N (N < 100)，隨後 N(N-1)/2 行邊信息（村莊編號、距離），N=0 結束
• 輸出：每組用例輸出最小公路總長度

樣例解析

輸入：
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

輸出：
3
5

第一組（3 個村莊）

邊：1-2(1), 1-3(2), 2-3(4)

MST 選擇 1-2 和 1-3，總長度 = 1 + 2 = 3

第二組（4 個村莊）

邊：1-2(1), 1-3(4), 1-4(1), 2-3(3), 2-4(2), 3-4(5)

MST 選擇 1-2(1), 1-4(1), 2-4(2) 或 1-2(1), 1-4(1), 2-3(3) → 最小為 1+1+2=4? 等等...

實際最優：1-2(1), 1-4(1), 2-4(2) 形成環，不可取。正確選擇：1-2(1), 1-4(1), 2-3(3) → 總長 5。樣例輸出 5 驗證正確。

算法選擇：Prim vs Kruskal

Prim 算法（適合稠密圖，本題適用）

• 時間複雜度：O(N²) 邻接矩陣實現
• 核心思想：從任意節點開始，貪心選擇連接樹外節點的最小邊

Kruskal 算法（適合稀疏圖）

• 時間複雜度：O(E log E) 排序邊 + 并查集
• 核心思想：將所有邊按權值排序，依次加入不形成環的邊

Prim 算法 C++ 實現

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int MAXN = 105;
const int INF = INT_MAX;

int n;
int graph[MAXN][MAXN];
int dist[MAXN];
bool visited[MAXN];

int prim() {
    fill(dist, dist + n + 1, INF);
    fill(visited, visited + n + 1, false);
    dist[1] = 0;
    int total = 0;

    for (int i = 1; i <= n; ++i) {
        int u = -1, minDist = INF;
        for (int j = 1; j <= n; ++j) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        if (u == -1) break; // 圖不連通
        visited[u] = true;
        total += minDist;
        for (int v = 1; v <= n; ++v) {
            if (!visited[v] && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v];
            }
        }
    }
    return total;
}

int main() {
    while (cin >> n && n) {
        fill(&graph[0][0], &graph[0][0] + MAXN * MAXN, INF);
        int edges = n * (n - 1) / 2;
        for (int i = 0; i < edges; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u][v] = graph[v][u] = w;
        }
        cout << prim() << endl;
    }
    return 0;
}

關鍵點總結

1. 圖的表示：鄰接矩陣適合 N<100 的稠密圖
2. 初始化：距離數組設為 INF，起點設為 0
3. 貪心選擇：每輪選未訪問節點中距離最小者
4. 更新鄰居：放寬鄰居節點到樹的距離
5. 多測試用例：循環讀取直到 N=0

擴展思考

• 若圖不連通，MST 不存在，需檢測並處理
• 邊權可能為 0 或負數？Prim/Kruskal 仍適用
• 輸出具體修建方案？需記錄父節點數組

這道題是圖論入門的經典必刷題，掌握 Prim 算法的矩陣實現是解決此類問題的關鍵。