最小生成樹教學：Kruskal 與 Prim 演算法

最小生成樹解決什麼問題

假設你要用電纜連接幾棟建築、用道路連接幾個城鎮，或用網路線連接幾台伺服器，而每種可能的連線都有成本。你希望每個地方都（直接或間接）連通，且總成本最低。形成迴圈的多餘連線永遠不需要，所以答案是一棵樹：V 個節點恰好由 V − 1 條邊連接，這棵樹就是最小生成樹。

MST 不是最短路徑樹。它最小化的是所有邊的總權重，而不是從單一起點到其他節點的距離。

為什麼貪婪選擇有效：切割性質

把節點分成任意兩組。在跨越兩組的邊之中，最輕的那條屬於某棵最小生成樹。兩種演算法都依賴這個事實：

如果所有邊的權重都不同，MST 就是唯一的，所以兩種演算法會回傳相同的樹。權重相同時，可能有多棵總權重相同的 MST。

逐步範例

無向圖有 5 個節點，邊為 A–B 4、A–C 3、B–C 1、B–D 2、C–D 4、D–E 2、C–E 5。

Kruskal 演算法，邊依權重排序：

從 A 開始的 Prim 演算法：離開 {A} 的最便宜邊是 A–C（3）；從 {A, C} 出發是 C–B（1）；從 {A, B, C} 出發是 B–D（2）；從 {A, B, C, D} 出發是 D–E（2）。得到相同的樹，總權重為 3 + 1 + 2 + 2 = 8。

Python 的 Kruskal 演算法

Union-find 為每個節點保存一個父節點指標。find 回傳節點所屬元件的代表，兩個節點相連，當且僅當它們有相同的代表。

def kruskal(nodes, edges):
    parent = {n: n for n in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x

    tree, total = [], 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:                          # different components: no cycle
            parent[ru] = rv
            tree.append((u, v, w))
            total += w
    return tree, total

nodes = "ABCDE"
edges = [(4, "A", "B"), (3, "A", "C"), (1, "B", "C"), (2, "B", "D"),
         (4, "C", "D"), (2, "D", "E"), (5, "C", "E")]
print(kruskal(nodes, edges))
# ([('B', 'C', 1), ('B', 'D', 2), ('D', 'E', 2), ('A', 'C', 3)], 8)

完整的 union-find 還會使用按秩或按大小合併，讓樹保持扁平。光是路徑減半在實務上就已經很快。當樹已有 V − 1 條邊時，可以提前結束迴圈。

Python 的 Prim 演算法

Prim 演算法需要鄰接串列。它和 Dijkstra 演算法一樣使用惰性刪除：推入每條離開這棵樹的邊，並略過遠端已在樹中的邊。

import heapq
from collections import defaultdict

def prim(edges, start):
    graph = defaultdict(list)
    for w, u, v in edges:
        graph[u].append((w, u, v))
        graph[v].append((w, v, u))
    in_tree = {start}
    heap = list(graph[start])
    heapq.heapify(heap)
    tree, total = [], 0
    while heap:
        w, u, v = heapq.heappop(heap)
        if v in in_tree:
            continue
        in_tree.add(v)
        tree.append((u, v, w))
        total += w
        for edge in graph[v]:
            if edge[2] not in in_tree:
                heapq.heappush(heap, edge)
    return tree, total

print(prim(edges, "A"))
# ([('A', 'C', 3), ('C', 'B', 1), ('B', 'D', 2), ('D', 'E', 2)], 8)

時間與空間複雜度

因為 E 至多為 V²，log E 至多為 2 log V，所以 O(E log E) 與 O(E log V) 是同一個數量級。

變化版本與常見錯誤

• 非連通圖：不存在生成樹。這時 Kruskal 會回傳最小生成森林（每個元件一棵樹）；從單一起點執行的 Prim 只會涵蓋該起點所在的元件。請檢查樹是否有 V − 1 條邊。
• 最大生成樹：將邊依降序排序（或把權重取負）。這兩種演算法都可以處理負權重。
• 有向圖需要另一種演算法（最小樹形圖，Chu-Liu/Edmonds）；Kruskal 和 Prim 不適用。
• 分群：執行 Kruskal，剩下 k 個元件時停止。結果就是分成 k 群的單連結分群。
• 1926 年的 Borůvka 演算法一次對每個元件加入其最便宜的邊，很適合平行化。

何時使用與實際應用

• 網路設計：在任何連通的配置都可接受時，以最便宜的方式用電纜、管線或道路連接各個據點。
• 近似演算法：MST 可為度量旅行推銷員問題提供長度至多為最佳解兩倍的路線。
• 分群與影像分割：切掉 MST 中最重的邊。
• 面試題目：連接所有點的最小成本、以最小成本連接城市、最佳化村莊的供水配置。