跳轉到

9.3 最小生成樹Kruskal與Prim#

概念說明#

最小生成樹（Minimum Spanning Tree, MST）：給定連通的無向加權圖，挑出 V−1 條邊把所有頂點連起來，且總權重最小。應用：拉網路線、鋪水管、電路布線、影像分割。

兩個演算法都基於貪心與切割性質：把頂點分成兩堆時，橫跨兩堆的最輕邊一定在某棵 MST 裡。

  • Kruskal：全域視角——把所有邊按權重由小到大排序，逐一嘗試加入；用併查集判斷「加入會不會成環」，成環就跳過。選滿 V−1 條即完成。
  • Prim：局部擴張——從任一點出發，維護「已連通集合」，用最小堆積不斷挑出「連到外部」的最輕邊，把新點吸進來。像 Dijkstra，但比較的是「邊權」而非「起點到點的總距離」。

操作步驟#

Kruskal： 1. 所有邊依權重排序。 2. 依序取邊 (u, v)：若 find(u) != find(v)，加入答案並 union(u, v)；否則捨棄（會成環）。 3. 累計 V−1 條即停。

Prim： 1. 起點的邊全入堆積，標記起點已連通。 2. 堆積取出最輕邊 (w, u, v)：若 v 已連通則丟棄；否則加入答案、標記 v，把 v 的邊推入堆積。 3. 直到連通 V 個點。

Python 實作#

import heapq

# ---------- Kruskal ----------
def kruskal(n, edges):                 # edges: [(w, u, v), ...]
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # 路徑壓縮（減半）
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
        return True

    total = 0
    mst = []
    for w, u, v in sorted(edges):          # 依權重排序
        if union(u, v):
            total += w
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break
    return total, mst

# ---------- Prim ----------
def prim(graph, start=0):                # graph: {u: [(v, w), ...]}
    visited = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    total, mst = 0, []
    while pq and len(visited) < len(graph):
        w, u, v = heapq.heappop(pq)
        if v in visited:
            continue
        visited.add(v)
        total += w
        mst.append((u, v, w))
        for nb, w2 in graph[v]:
            if nb not in visited:
                heapq.heappush(pq, (w2, v, nb))
    return total, mst

# 校園布線：5 棟大樓
edges = [
    (4, 0, 1), (1, 0, 2), (3, 1, 2), (2, 1, 3), (5, 2, 3),
    (7, 2, 4), (6, 3, 4),
]
cost1, mst1 = kruskal(5, edges)
print("Kruskal 成本:", cost1)            # 12
print("選出的邊:", sorted(mst1))

graph = {0: [(1, 4), (2, 1)],
         1: [(0, 4), (2, 3), (3, 2)],
         2: [(0, 1), (1, 3), (3, 5), (4, 7)],
         3: [(1, 2), (2, 5), (4, 6)],
         4: [(2, 7), (3, 6)]}
cost2, mst2 = prim(graph)
print("Prim 成本:", cost2)               # 12（兩者必相同）
print("選出的邊:", mst2)

兩者的取捨#

Kruskal Prim
資料結構 排序 + 併查集 最小堆積 + 相鄰串列
時間 O(E log E) O((V+E) log V)（堆積版）
適合 稀疏圖、邊已排序/邊串列給定 稠密圖、相鄰串列給定
思路 「全圖最輕的邊逐條考慮」 「從種子點往外長」

複雜度分析#

Kruskal：排序 O(E log E) 主導；併查集操作近 O(1)。Prim（堆積）：每條邊至多 push 一次，堆積操作 O(log E)。兩者空間皆 O(V + E)。若邊權範圍小，Kruskal 可用計數排序；稠密圖上 Prim 的「陣列版」為 O(V²) 反而更快。

練習#

  1. 修改 Kruskal：不要求連通（森林情況），回傳最小生成森林，並說明當圖不連通時兩個演算法各會發生什麼。
  2. 實作 Prim 的陣列版（不用堆積，每輪線性掃描找最近的未連通點），複雜度 O(V²)；在 V=500、E=60000 的稠密圖上與堆積版比較速度。
  3. 證明練習：用切割性質論證 Kruskal 的正確性——為什麼「不成環的最輕邊」橫跨了某個切割？