C語言解決「暢通工程」最小生成樹問題：Prim/Kruskal 算法完整實現

問題建模

• 圖：N 個村莊 (頂點)，N(N-1)/2 條邊 (完全圖)，邊權為距離。
• 目標：選取 N-1 條邊連通所有頂點，邊權和最小 → **最小生成樹 (MST)**。
• 輸入多組測試用例，N=0 結束。

算法選擇：Prim (鄰接矩陣) 適合稠密圖

完全圖邊數 ~ O(N²)，Prim + 鄰接矩陣 O(N²) 最優；Kruskal 需排序 O(E log E) = O(N² log N) 稍慢。

Prim 算法完整代碼 (C99 標準)

#include <stdio.h>
#include <limits.h>

#define MAXN 100
#define INF INT_MAX

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

int prim(int n) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[0] = 0;          // 從頂點 0 開始
    int total = 0;

    for (int iter = 0; iter < n; iter++) {
        // 1. 選擇未訪問、距離最小的頂點 u
        int u = -1, minDist = INF;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                u = i;
            }
        }
        if (u == -1) break; // 圖不連通 (按題意不會發生)
        visited[u] = 1;
        total += dist[u];

        // 2. 更新鄰居距離
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v];
            }
        }
    }
    return total;
}

int main() {
    int N;
    while (scanf("%d", &N) == 1 && N != 0) {
        // 初始化鄰接矩陣
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                graph[i][j] = (i == j) ? 0 : INF;

        // 讀取 N(N-1)/2 條邊
        int edges = N * (N - 1) / 2;
        for (int k = 0; k < edges; k++) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            u--; v--;               // 題目編號 1~N → 數組 0~N-1
            graph[u][v] = graph[v][u] = w;
        }

        printf("%d\n", prim(N));
    }
    return 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

解析樣例 1：選邊 (1,2)=1, (1,3)=2，總權 3。原帖質疑「2-3 距離 4 但公路只需 3」正是 MST 核心——**不要求直接相連，只需通過其他村莊間接通達**。

Kruskal 算法備選實現 (並查集)

struct Edge {int u, v, w;};
int parent[MAXN];
int find(int x) { return parent[x]==x ? x : (parent[x]=find(parent[x])); }
void unite(int a, int b) { parent[find(a)] = find(b); }

int kruskal(int n, struct Edge *edges, int m) {
    for (int i = 0; i < n; i++) parent[i] = i;
    // 按權重升序排序
    qsort(edges, m, sizeof(struct Edge),
          (int(*)(const void*,const void*))[](const void* a, const void* b) {
              return ((struct Edge*)a)->w - ((struct Edge*)b)->w;
          });
    int total = 0, cnt = 0;
    for (int i = 0; i < m && cnt < n-1; i++) {
        if (find(edges[i].u) != find(edges[i].v)) {
            unite(edges[i].u, edges[i].v);
            total += edges[i].w;
            cnt++;
        }
    }
    return total;
}

複雜度對比

常見坑點提示

1. 下標轉換：輸入村莊編號 1~N，數組 0~N-1，必須 u--; v--;。
2. 多測試用例循環：while (scanf("%d", &N) && N) 正確處理 N=0 終止。
3. 初始化 INF：用 INT_MAX 或足夠大的常數 (如 0x3f3f3f3f)，避免溢出。
4. 圖不連通：題目保證完全圖，但通用代碼應檢查 u==-1 或 cnt。