Prim 演算法

Prim 演算法是另一種找 MST 的方法，從一個起點開始，每次加入最近的未連接節點。

Vibe Prompt

「幫我用 Prim 演算法找出隨機 20 個點的最小生成樹，用 Matplotlib 畫出 MST。」

import heapq, math, random, matplotlib.pyplot as plt

def prim(points):
    n = len(points)
    visited = [False] * n
    pq = [(0, 0, -1)]  # (cost, node, parent)
    mst = []
    total = 0
    
    while pq:
        cost, node, parent = heapq.heappop(pq)
        if visited[node]:
            continue
        visited[node] = True
        total += cost
        if parent != -1:
            mst.append((parent, node, cost))
        for neighbor in range(n):
            if not visited[neighbor]:
                dx = points[node][0] - points[neighbor][0]
                dy = points[node][1] - points[neighbor][1]
                dist = math.sqrt(dx*dx + dy*dy)
                heapq.heappush(pq, (dist, neighbor, node))
    return mst, total

random.seed(42)
pts = [(random.random()*100, random.random()*100) for _ in range(20)]
mst, total = prim(pts)
print(f"MST 總長: {total:.2f}")

深入理解：Prim 演算法的正確性

割性質 (Cut Property)

Prim 演算法的正確性建立在割性質之上：

對於圖中任意一個割（將節點分為兩組），**權重最小的跨越邊（crossing edge）**一定屬於某個 MST。

Prim 每次加入的邊，正是目前已拜訪集合與未拜訪集合之間的最小跨越邊，因此保證正確。

Prim 的三種實作方式

| 實作 | 時間複雜度 | 適用場景 | |------|:---------:|---------| | 鄰接矩陣 + 陣列 | $O(n^2)$ | 密集圖首選 | | 鄰接串列 + Binary Heap | $O(m \log n)$ | 通用選擇 | | 鄰接串列 + Fibonacci Heap | $O(m + n \log n)$ | 超大圖理論最佳 |

MST 的實際應用

網路設計：佈線、光纖網路的最小成本連接
叢集分析：移除 MST 的最長邊進行分群
影像分割：基於 MST 的像素分群
旅行推銷員近似：MST 的 2-approximation

關鍵要點

✅ Prim 從起點逐步擴張，每次加入最近的未連接節點
✅ 正確性由割性質保證
✅ 使用 Binary Heap 實作得到 $O(m \log n)$
✅ 密集圖用鄰接矩陣實作 $O(n^2)$ 反而更快
✅ Kruskal（邊排序）與 Prim（點擴張）各有適合場景

常見錯誤

程式碼範例

Prim 為什麼是最短路線之王？

Prim 演算法解決的是**最小生成樹（MST）**問題：用最少的總成本連接所有節點。這在真實世界中有非常直接的應用：

真實世界的 MST

| 應用 | 節點 | 邊 | 成本 | |:----|:----|:---|:----| | 網路佈線 | 電腦 | 網路線 | 纜線長度 × 單價 | | 電路設計 | 晶片接腳 | 導線 | 導線長度 | | 管線配置 | 建築物 | 水管/電管 | 管線材料費 | | 交通規劃 | 城市 | 公路 | 建設成本 | | 叢集分析 | 資料點 | 相似度 | 距離度量 |

Kruskal vs Prim：什麼時候用哪個？

| 比較 | Kruskal | Prim | |:----|:-------|:-----| | 策略 | 排序所有邊，從小到大選取 | 從起點擴展，每次加最近的節點 | | 資料結構 | Union-Find | Priority Queue (Min-Heap) | | 時間複雜度 | O(E log E) | O(E log V) | | 適合 | 邊較少的稀疏圖 | 邊較多的稠密圖 | | 實作難度 | 中等（需要 Union-Find） | 中等（需要 Heap） |

Prim 的核心思想

Prim 的每一步都在做同一件事：從已連接的節點集合出發，找到一條通往未連接節點的最短路徑。這就是貪婪策略的典型應用——每次做當下最好的選擇，最終卻能得到全域最佳解。MST 是少數貪婪 = 最佳的數學證明案例。

下一章預告：Huffman 編碼

MST 展示了貪婪演算法在建構連通網路上的威力。下一章的 Huffman 編碼則展示了貪婪在資料壓縮上的應用——你會看到完全不同的問題型態，卻同樣可以用貪婪策略有效解決。