最小生成樹 Kruskal 算法 C 語言完整實現與工程化細節

算法原理回顧

Kruskal 算法屬於貪婪策略：將所有邊按權重升序排序，依次考慮每條邊，若其兩端點不在同一連通分量（不形成環），則加入 MST，並合併兩分量。核心子問題：並查集 維護動態連通性。

數據結構定義

typedef struct _node { char data; int flag; struct _node *parent; } node;\
typedef struct _edge { node *A, *B; int w; } edge;\
typedef struct _graph { node **nodelist; int nodeLen; edge **edgelist; int edgeLen; } graph;

核心函數實現

1. 並查集操作

int makeset(node *n) { n->parent = n; }\
\
int find(node *n, node *ds) {\
    if (n->parent == n) {\
        ds->data = n->data; ds->flag = 1; ds->parent = n->parent;\
    } else find(n->parent, ds);  // 遞歸查找根節點\
}\
\
int merge(node *da, node *db) {\
    if (da->flag) db->parent = da;\
    else da->parent = db;\
}

• makeset：每個節點自成一集，父指針指向自己。
• find：遞歸尋找根節點，將結果存入 ds（含 flag 標記是否為根）。未實現路徑壓縮，教學用途可接受。
• merge：根據 flag 將一棵樹掛到另一棵根下。

2. 邊比較函數（供 qsort）

int comp(const void *ea, const void *eb) {\
    int wa = (*(edge**)ea)->w;\
    int wb = (*(edge**)eb)->w;\
    return (wa > wb) - (wa < wb);  // 返回 1/0/-1\
}

3. Kruskal 主流程

int kruskal(graph *g, edge *X[]) {\
    for (int i = 0; i < g->nodeLen; ++i) makeset(g->nodelist[i]);\
    qsort(g->edgelist, g->edgeLen, sizeof(edge*), comp);\
    \
    node da, db; da.parent = malloc(sizeof(node)); db.parent = malloc(sizeof(node));\
    for (int j = 0; j < g->edgeLen; ++j) {\
        find(g->edgelist[j]->A, &da);\
        find(g->edgelist[j]->B, &db);\
        if (da.data != db.data) {  // 不同集合\
            merge(g->edgelist[j]->A, g->edgelist[j]->B);\
            *X++ = g->edgelist[j];  // 加入 MST\
        }\
    }\
}

測試圖構建與輸出

6 個節點 (a-f)，10 條邊，手動構建鄰接表。運行輸出展示排序後邊列表與最終 MST 邊：

a-b 5\
a-c 6\
a-d 4\
b-c 1\
b-d 2\
c-d 2\
c-e 5\
c-f 3\
d-f 4\
e-f 4\
--------------------\
b-c 1\
b-d 2\
c-f 3\
a-d 4\
e-f 4\
--------------------

MST 總權重 = 1+2+3+4+4 = 14，包含 5 條邊 (n-1)。

關鍵工程細節與改進點

1. 內存洩漏：da.parent/db.parent 分配未釋放；節點 parent 初始化分配未釋放。生產代碼需配對 free。
2. 並查集優化：引入路徑壓縮（find 時將沿途節點直掛根下）與按秩合併（rank 數組記錄樹高），時間複雜度趨近 O(α(n))。
3. 邊存儲優化：使用連續數組 edge edges[] 代替指針數組，提高緩存局部性。
4. 錯誤處理：malloc/qsort 返回值檢查。
5. 測試驗證：作者強調「程序能編譯只是小部分，必須反復測試才能發布」，體現工程師思維。

應用場景拓展

• 網絡佈線、電路設計、聚類分析（單鏈聚類本質即 Kruskal）。
• 稀疏圖首選 Kruskal (O(E log E))，稠密圖 Prim (O(V²) 或 O(E+V log V)) 更優。

此實現雖為教學簡化版，但完整呈現了 Kruskal 算法的核心骨架：排序邊、並查集判環、貪婪選擇，是理解 MST 與並查集的優秀入門代碼。