手把手寫演算法：Kruskal 最小生成樹完整實現（上）

Kruskal 演算法是另一種經典的最小生成樹 (MST) 演算法。與 Prim 以「節點為中心擴展」不同，Kruskal 以「邊為中心」處理：將所有邊按權重排序，依序加入，若不形成環則納入。本文從原理、範例演示到資料結構定義，完整鋪陳基礎。

核心邏輯

1. 將 m 個節點視為 m 棵獨立的樹（森林）
2. 將 n 條邊按權重升序排序
3. 依序取出邊 (u, v, w)：
   • 若 u、v 屬於不同樹 → 合併兩樹，納入此邊
   • 若 u、v 屬於同一樹 → 捨棄此邊（會形成環）
4. 重複直到所有邊處理完畢或樹合併為單一棵

圖解範例演示

四節點圖：A-B(6)、A-C(7)、A-D(3)、B-C(5)、B-D(9)

初始森林：  A   B   C   D  (四棵獨立樹)
邊排序：    A-D(3) → B-C(5) → A-B(6) → A-C(7) → B-D(9)

步驟1：加入 A-D(3)  →  樹1: A-D    樹2: B    樹3: C
步驟2：加入 B-C(5)  →  樹1: A-D    樹2: B-C
步驟3：加入 A-B(6)  →  樹1: A-D-B-C (A、B屬不同樹，合併)
步驟4：A-C(7) 捨棄  →  A、C已在同樹
步驟5：B-D(9) 捨棄  →  B、D已在同樹

最終 MST：A-D(3)、B-C(5)、A-B(6)  總權重 14

資料結構定義（沿用 Prim 設計）

// 有向邊（MST 中的邊）
typedef struct _DIR_LINE {
    int start, end, weight;
    struct _DIR_LINE* next;
} DIR_LINE;

// 最小生成樹
typedef struct _MINI_GENERATE_TREE {
    int node_num, line_num;
    int* pNode;        // 節點集合
    DIR_LINE* pLine;   // 邊鏈表
} MINI_GENERATE_TREE;

// 圖的鄰接表表示
typedef struct _LINE {      // 鄰接邊
    int end, weight;
    struct _LINE* next;
} LINE;

typedef struct _VECTEX {    // 頂點
    int start, number;
    LINE* neighbor;
    struct _VECTEX* next;
} VECTEX;

typedef struct _GRAPH {     // 圖
    int count;
    VECTEX* head;
} GRAPH;

Kruskal 關鍵挑戰

Prim 只需維護單一樹的擴展，Kruskal 需同時管理多棵樹的動態合併，核心難點在於：

1. 邊排序：對結構體陣列/鏈表按權重排序
2. 樹查找：快速判斷兩節點屬於哪棵樹
3. 樹合併：高效合併兩棵樹的節點與邊集合

傳統陣列實現合併效率低，並查集 (Union-Find) 是標準解法，可將查找與合併優化至近 O(1)。下篇將詳細實現排序、查找、合併三大核心模組。

對比總結：Prim vs Kruskal

理解兩種演算法的異同，能根據圖的特性選擇最優方案。