Kruskal 與 Union-Find

Union-Find 實作

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路徑壓縮
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        # 按秩合併
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

Kruskal MST

def kruskal(n, edges):
    """
    n: 節點數量
    edges: (u, v, weight)
    """
    edges.sort(key=lambda x: x[2])  # 按權重排序
    uf = UnionFind(n)
    mst = []
    total = 0
    
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total += w
    
    return mst, total

Vibe Prompt

🔥 詠唱：「請用隨機產生的 50 個城市座標，實作 Kruskal MST 並用 Matplotlib 畫出生成樹。」

深入理解：Union-Find 的時間複雜度

Union-Find 搭配路徑壓縮 + 按秩合併後的時間複雜度近乎常數：

| 操作 | 未優化 | 路徑壓縮 | 路徑壓縮 + 按秩合併 | |------|:------:|:--------:|:------------------:| | find() | $O(n)$ | $O(\log n)$ | $O(\alpha(n))$ 攤銷 | | union() | $O(n)$ | $O(\log n)$ | $O(\alpha(n))$ 攤銷 | | Kruskal 總體 | $O(m \log m)$ | $O(m \log n)$ | $O(m \log n)$ |

$\alpha(n)$ 是反阿克曼函數，對於任何實際的 $n$，$\alpha(n) \leq 4$

Kruskal vs Prim 比較

| 特性 | Kruskal | Prim | |------|:-------:|:----:| | 演算法類型 | 邊為基礎 | 點為基礎 | | 適合 | 稀疏圖 ($m \approx n$) | 密集圖 ($m \approx n^2$) | | 資料結構 | Union-Find | 最小堆積 (Priority Queue) | | 時間複雜度 | $O(m \log m)$ | $O(m \log n)$ | | 是否需要連通 | 不需要 | 需要連通圖 |

關鍵要點

✅ Kruskal 演算法：按權重排序邊，用 Union-Find 避免環
✅ Union-Find 路徑壓縮 + 按秩合併 = 近乎 O(1) 的操作
✅ Kruskal 適合稀疏圖，Prim 適合密集圖
✅ MST 的最小性證明：割性質 (Cut Property)
✅ MST 在網路設計、叢集分析中有廣泛應用

Union-Find 的實戰應用：不只是 Kruskal

Union-Find（Disjoint Set）是你學過最實用但最被低估的資料結構。它不只用在 Kruskal 演算法——任何需要「動態分組」或「偵測連通性」的場景，Union-Find 都是最佳選擇。

真實世界的 Union-Find 應用

| 應用 | 問題 | Union-Find 的角色 | |:----|:----|:----------------| | 社群網路好友推薦 | A 是 B 的好友，B 是 C 的好友 → A、B、C 同一群組 | 維護朋友圈的連通分量 | | 圖片像素連通域 | 找出圖片中所有相連的相同顏色區域 | 合併相鄰的同色像素 | | 迷宮生成與求解 | 隨機打通牆壁直到起點終點連通 | 偵測兩點是否已經連通，避免產生環 | | 電路板短路檢測 | 兩個接腳是否屬於同一網路 | 合併相連的節點，查詢連通性 | | 資料庫合併 | 兩筆紀錄是否屬於同一個人 | 合併相同人的 ID |

為什麼 Union-Find 這麼快？

路徑壓縮（Path Compression）+ 按秩合併（Union by Rank）讓 Union-Find 的攤銷時間複雜度變成 O(α(n))，而反阿克曼函數 α(n) 對於任何實際的 n 都小於 5。

換句話說，Union-Find 的操作可以視為 O(1)——這是理論上你能得到的最快速度。

下一章預告：Prim 演算法

Kruskal 是「以邊為中心」的 MST 演算法，而 Prim 是「以點為中心」——從起點出發，每一步加入最近的節點。下一章你將學到 Prim 搭配 Priority Queue 的實作，以及 Kruskal 與 Prim 各自的適用場景。