在 Day 26 我們介紹了 最小生成樹 (MST) 的概念，並且在 Day 27 深入探討了 Kruskal 演算法。今天要介紹的是另一個經典方法 —— Prim 演算法。它與 Kruskal 不同，Prim 是以 節點為導向 的最小生成樹演算法。

演算法原理

Prim 演算法的核心思想是: 從某個節點開始，每次選取一條 最小權重的邊，將新的節點加入生成樹，直到所有節點都被包含。

這是一種貪心演算法 (Greedy Algorithm)。它與 Dijkstra 有相似之處: 都是透過優先佇列 (Min-Heap) 逐步擴展搜尋範圍。

演算法步驟

• 從任意一個節點作為起點，初始化生成樹集合 MST = {}
• 將所有與起點相連的邊放入優先佇列 (Min-Heap)
• 每次從堆中取出最小權重邊，若該邊連接的節點尚未在 MST，則將其加入
• 將該節點的新邊加入堆中
• 重複步驟 3–4，直到所有節點都被加入 MST

Python 實作

import heapq

def prim(graph, start=0):
    """
    graph: adjacency list 格式 {u: [(v, w), ...]}
    start: 起點
    """
    V = len(graph)
    visited = [False] * V
    mst = []
    pq = [(0, start, -1)]  # (權重, 當前節點, 來源節點)

    while pq:
        w, u, parent = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        if parent != -1:
            mst.append((parent, u, w))

        for v, weight in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (weight, v, u))

    return mst


# 測試
graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}

mst = prim(graph, 0)
print("Prim MST:", mst)
# 輸出: [(0, 3, 5), (2, 3, 4), (0, 1, 10)]

複雜度分析

• 時間複雜度: 使用 Min-Heap，時間為 $O(E \log V)$
• 空間複雜度: 需要存 visited 陣列與優先佇列，為 $O(V + E)$

Prim 特別適合稠密圖 (Dense Graph)，因為它會不斷操作鄰接邊集合

Prim vs Kruskal

結語

Prim 與 Kruskal 雖然思路不同，但它們的目標都是構造出 最小生成樹。

• Kruskal 適合 稀疏圖，因為它需要排序邊
• Prim 適合 稠密圖，因為它逐步擴展節點

透過這兩個演算法的比較，我們不僅理解了 MST 的本質，也能根據不同場景靈活選擇方法