C 語言演算法實作：貪婪算法求最小生成樹（Kruskal、Prim、Sollin）

編輯：關於C語言

前言

最小生成樹（Minimum Spanning Tree, MST）是圖論中的經典問題：給定一個帶權無向連通圖，尋找一棵包含所有頂點、邊權總和最小的生成樹。本文介紹三種基於貪婪策略的演算法——Kruskal、Prim 與 Sollin，並提供 C++ 實作細節與複雜度分析。

問題定義

輸入：無向連通圖 G = (V, E)，|V| = n，|E| = e，每條邊有權重 w(u,v)
輸出：生成樹 T ⊆ E，|T| = n-1，使 Σ w(e) 最小化

Kruskal 演算法

核心思想

將所有邊按權重遞增排序，依序考慮每條邊：若加入該邊不形成環路，則納入生成樹；否則捨棄。重複直到樹包含 n-1 條邊或邊集耗盡。

偽代碼

T ← ∅
將 E 依權重遞增排序
for each (u,v) in E:
    if T ∪ {(u,v)} 不形成環路:
        T ← T ∪ {(u,v)}
    if |T| = n-1: break
return T

正確性證明

使用「切割性質」：對任意切割，權重最小的橫切邊必屬於某棵 MST。Kruskal 每次選擇當前最小且不成環的邊，符合切割性質，故能構建 MST。

資料結構與複雜度

操作	資料結構	時間複雜度
邊排序	最小堆 / 快速排序	O(e log e)
環路檢測	Union-Find (不相交集合)	O(α(n)) ≈ O(1) 攤還
合併集合	Union-Find (按秩合併+路徑壓縮)	O(α(n))

總複雜度： O(e log e) = O(e log n)（因 e ≤ n²）

C++ 實作關鍵點

template <class T>
struct EdgeNode {
    T weight;
    int u, v;
    operator T() const { return weight; }  // 支援堆比較
};

template <class T>
bool UNetwork<T>::Kruskal(EdgeNode<T> t[]) {
    int n = Vertices();
    int e = Edges();
    
    // 1. 收集所有邊
    EdgeNode<T> *E = new EdgeNode<T>[e+1];
    int k = 0;
    InitializePos();
    for (int i = 1; i <= n; i++) {
        int j; T c;
        First(i, j, c);
        while (j) {
            if (i < j) {  // 避免重複（無向圖）
                E[++k].weight = c;
                E[k].u = i; E[k].v = j;
            }
            Next(i, j, c);
        }
    }
    
    // 2. 建立最小堆
    MinHeap<EdgeNode<T>> H(1);
    H.Initialize(E, e, e);
    
    // 3. Union-Find 初始化
    UnionFind U(n);
    
    // 4. 貪婪選擇
    k = 0;
    while (e > 0 && k < n-1) {
        EdgeNode<T> x;
        H.DeleteMin(x);
        e--;
        int a = U.Find(x.u);
        int b = U.Find(x.v);
        if (a != b) {  // 不成環
            t[k++] = x;
            U.Union(a, b);
        }
    }
    
    DeactivatePos();
    H.Deactivate();
    delete[] E;
    return (k == n-1);
}

Prim 演算法

核心思想

從任一頂點開始，維護一棵「部分生成樹」。每步選擇一條連接樹內頂點與樹外頂點、權重最小的邊加入樹中。重複 n-1 次。

偽代碼

TV ← {1}  // 樹內頂點集合
T ← ∅
while |T| < n-1:
    選擇 (u,v) 使 u∈TV, v∉TV, w(u,v) 最小
    if 不存在這樣的邊: break  // 圖不連通
    T ← T ∪ {(u,v)}
    TV ← TV ∪ {v}
return T

優化實作：最近鄰陣列

維護陣列 near[v] 記錄樹外頂點 v 到樹內最近的頂點，以及 cost[v] = w(v, near[v])。每次選擇 cost[v] 最小的 v 加入。

複雜度

鄰接矩陣 + 線性搜尋：O(n²)
鄰接表 + 最小堆：O(e log n)
Fibonacci 堆：O(e + n log n)

Sollin 演算法（Borůvka 演算法）

核心思想

並行化思想：初始每個頂點為一棵樹（森林）。每輪中，每棵樹同時選擇連接自身的最小權重邊。所有被選邊加入森林，合併相連樹。重複直到只剩一棵樹。

流程示例

初始：7 個單點樹

第 1 輪：各點選最小邊 → (1,6)、(2,7)、(3,4)、(5,4) → 形成 3 棵樹

第 2 輪：3 棵樹各選最小邊 → (6,5)、(2,3) → 合併為 1 棵樹（MST 完成）

特點

天然適合並行計算
輪數 ≤ log₂ n
複雜度 O(e log n)
歷史上最早的 MST 演算法（1926 年）

三種演算法比較

演算法	時間複雜度	空間複雜度	適用場景	並行化
Kruskal	O(e log e)	O(e)	稀疏圖、邊已排序	困難（順序依賴）
Prim (堆)	O(e log n)	O(n+e)	稠密圖、動態圖	部分可並行
Sollin	O(e log n)	O(n+e)	並行環境、分散式系統	優秀（天然並行）