Kruskal 最小生成樹

🎯 什麼情境該想到我

當你「要用最小的總成本把所有節點連起來」的時候——網路佈線、道路規劃、電網、叢集分析（單連結聚類）、影像分割。
★ 它是貪婪演算法有嚴格證明的代表作，而證明的關鍵叫割性質。

⚙️ 怎麼用（機制、證明與實作）

定義

最小生成樹（MST）：連通無向圖的一個子集，連通所有節點、無環、總邊權最小。
$V$ 個節點的生成樹恰有 $V - 1$ 條邊。

Kruskal：按邊排序，能加就加

1. 把所有邊按權重由小到大排序
2. 依序考慮每條邊 (u,v)：
     ★ 如果 u 和 v 還不連通 → 加入 MST
       否則（加了會成環）→ 跳過
3. 加滿 V-1 條邊就完成

func Kruskal(edges []edge, n int) (mst []edge, total int) {
    slices.SortFunc(edges, func(a, b edge) int { return a.w - b.w })
    dsu := NewDSU(n)                       // 見 [[併查集]]
    for _, e := range edges {
        if dsu.Union(e.from, e.to) {       // ★ Union 回傳 false = 已連通 = 會成環
            mst = append(mst, e)
            total += e.w
            if len(mst) == n-1 { break }   // ★ 提前結束
        }
    }
    return mst, total
}

★ 「會不會成環」這個判斷就是併查集的主要用途。
用深度優先搜尋判斷每條邊會不會成環是 $O (E \cdot V)$ ；用併查集是實質 $O (E)$ 。

★ 為什麼貪婪是對的：割性質（Cut Property）

割性質：對圖的任意一種「割」（把節點分成兩個非空集合 $S$ 與 $V ∖ S$ ），
橫跨這個割的所有邊之中，權重最小的那一條必定屬於某棵 MST。

證明（交換論證，見貪婪演算法）：
設跨割的最小邊是 $e$ ，假設某棵 MST $T$ 不含 $e$ 。
把 $e$ 加進 $T$ 會形成一個環，而這個環必定還有另一條跨割的邊 $e^{'}$ （因為環要出去也要回來）。
由於 $e$ 是跨割最小的， $w (e) \leq w (e^{'})$ 。
用 $e$ 換掉 $e^{'}$ → 仍是生成樹，且總權重不增加 → 也是一棵 MST。∎

Kruskal 怎麼用到它：當演算法考慮邊 $e = (u, v)$ 且 $u, v$ 尚未連通時，
取 $S$ = 「 $u$ 所在的連通分量」。所有比 $e$ 小的跨割邊都已經被處理過了（因為按權排序），
而它們沒有連通 $u$ 和 $v$ → 所以 $e$ 就是此刻跨割的最小邊 → 由割性質，加它是安全的。

複雜度

$O (E lo g E) + O (E α (V)) = O (E lo g E)$

★ 排序是瓶頸，併查集那部分實質是線性的（見併查集的 $α (n) < 5$ ）。
（ $E \leq V^{2}$ 所以 $lo g E = O (lo g V)$ ，寫成 $O (E lo g V)$ 也對。）

★ Kruskal vs Prim

	Kruskal	Prim 最小生成樹
策略	按邊排序，全域挑最小	從一點長樹，挑最小的跨邊
中間狀態	森林（多棵樹同時長）	一棵樹（連通）
核心結構	併查集	二元堆積
複雜度	$O (E lo g E)$	$O (E lo g V)$ （堆）或 $O (V^{2})$ （陣列）
適合	★ 稀疏圖（ $E$ 小）	★ 稠密圖（用 $O (V^{2})$ 陣列版）
邊已排序時	$O (E α (V))$ 近乎線性	沒有這個好處
分散式	較容易（邊可以分散處理）	較難（要維護單一成長中的樹）

★ 實務判準：

邊少（ $E \approx V$ ）或邊本來就排好了 → Kruskal

邊多（ $E \approx V^{2}$ ）→ Prim 的 $O (V^{2})$ 陣列版（連堆都不用）

只是隨手寫一個 → Kruskal 比較好寫（排序 + 併查集，沒有堆的邊界處理）

實務應用

場景	說明
網路 / 電網 / 管線佈設	最小總成本連通
★ 單連結階層聚類	Kruskal 的過程就是單連結聚類：每次合併距離最近的兩個群
影像分割	像素當節點、顏色差當邊權，MST 上砍掉大邊就得到分割（Felzenszwalb 演算法）
★ 最小瓶頸路	MST 上的路徑同時也是最小瓶頸路（路徑上最大邊權最小）——一個好用的副產品
近似 TSP	MST 是旅行商問題的下界，可構造 2-近似解（見近似演算法）

🧪 我實際套用的紀錄

（待填）

⚠️ 注意 / 什麼時候不適用

★ 只適用於無向圖。有向圖的對應問題是「最小樹形圖（arborescence）」，要用 Chu–Liu/Edmonds 演算法，完全不同。
圖不連通時得到的是「最小生成森林」。要檢查 len(mst) == n-1，否則你的圖本來就連不起來。
邊權有重複時 MST 不唯一（但總權重唯一）。需要確定性結果就加一個 tie-breaker。
負權邊沒問題。MST 不受負權影響（不像最短路），因為它不涉及路徑累加。
★ 併查集的兩個優化都要做，否則退化成 $O (E lo g V)$ （雖然仍可接受）。
提前結束很重要：加滿 $V - 1$ 條就 break，稠密圖上能省下大量無用的迭代。
要「最大生成樹」就把排序反過來——同樣正確（割性質對稱成立）。

🔗 相關工具

Prim 最小生成樹 —— 另一種 MST 演算法，以及怎麼選
併查集 —— 成環判斷的核心結構
貪婪演算法 —— 割性質是交換論證的經典範例
快速排序 —— 排序是它的複雜度瓶頸
近似演算法 —— MST 用於 TSP 的 2-近似
演算法導論

Quartz 5

Explorer