Prim 最小生成樹

🎯 什麼情境該想到我

當你「要最小生成樹，而且圖是稠密的」的時候。
★ 它的程式碼和 Dijkstra 最短路徑 幾乎一模一樣——差別只有一行。理解那一行的差異，就同時理解了兩個演算法。

⚙️ 怎麼用（機制與對照）

Prim：從一個點開始，把樹長出去

1. 任選一個起點，樹 T = {起點}
2. 重複 V-1 次：
     ★ 在「一端在 T 內、另一端在 T 外」的所有邊中，挑權重最小的
     把那條邊和它的外側端點加入 T

和 Kruskal 最小生成樹 的差別：

Kruskal 的中間狀態是一片森林（很多棵小樹同時長），最後合併成一棵。
Prim 的中間狀態始終是一棵連通的樹，只是越長越大。

★ 正確性：同樣是割性質

取割 $S=T$（已在樹裡的點）、$V\setminus S$（樹外的點）。
Prim 每次挑的正是跨越這個割的最小邊 → 由割性質（證明見 Kruskal 最小生成樹），加它一定安全。

★ Kruskal 和 Prim 是「同一個定理的兩種用法」：
都靠割性質，只是選擇割的方式不同——Kruskal 用「連通分量」當割，Prim 用「已建好的樹」當割。

實作一：$O(V^2)$ 陣列版（★ 稠密圖首選）

// g 是鄰接矩陣，g[i][j] = 邊權（無邊為 INF）
func PrimDense(g [][]int, n int) int {
    const INF = math.MaxInt / 2
    minE := make([]int, n)          // minE[v] = v 連到樹的最小邊權
    inTree := make([]bool, n)
    for i := range minE { minE[i] = INF }
    minE[0] = 0
    total := 0
 
    for i := 0; i < n; i++ {
        // ★ 線性找出樹外距離最小的點 —— O(V)
        u := -1
        for v := 0; v < n; v++ {
            if !inTree[v] && (u == -1 || minE[v] < minE[u]) { u = v }
        }
        if minE[u] == INF { return -1 }     // 圖不連通
        inTree[u] = true
        total += minE[u]
        // ★ 用 u 更新所有樹外點的 minE —— O(V)
        for v := 0; v < n; v++ {
            if !inTree[v] && g[u][v] < minE[v] { minE[v] = g[u][v] }
        }
    }
    return total
}

★ 稠密圖上這個版本反而最快：$O(V^2)$，沒有堆、沒有配置、連續記憶體存取。
$E\approx V^2$ 時，堆版的 $O(E\log V)=O(V^2\log V)$ 反而更慢。

實作二：堆優化 $O(E\log V)$（稀疏圖）

把「線性找最小」換成 二元堆積，並用惰性刪除（同 Dijkstra 最短路徑）。

★ Prim vs Dijkstra：只差一行

// Dijkstra：到起點的「累積距離」
if dist[u] + w < dist[v] { dist[v] = dist[u] + w }
//         ^^^^^^^^^^^^ 累加
 
// Prim：到「樹」的單邊距離
if w < minE[v] { minE[v] = w }
//  ^ 不累加

	Dijkstra	Prim
dist/minE[v] 的意義	從起點到 $v$ 的最短路徑長	從 $v$ 連到樹的最小單邊權
鬆弛	dist[u] + w（累加）	w（不累加）
求什麼	最短路徑	最小生成樹
負權	❌ 會錯	✅ 沒問題

★ 「Prim 不受負權影響」的原因：它從不累加路徑長度，只比較單一邊權。
而 Dijkstra 的正確性建立在「路徑只會變長」上（見該頁的反例）。
這一行差異解釋了兩者所有的性質差異。

複雜度

實作	複雜度	適合
陣列	$O(V^2)$	★ 稠密圖（$E\approx V^2$）
二元堆	$O(E\log V)$	稀疏圖
Fibonacci heap	$O(E+V\log V)$	理論最優，實務不用

★ 怎麼選（與 Kruskal 對照）

情況	選
稠密圖（$E\approx V^2$）	Prim 陣列版 $O(V^2)$ —— 連堆都不用
稀疏圖（$E\approx V$）	Kruskal 最小生成樹 $O(E\log E)$
邊已經排好序	Kruskal（近乎線性）
只是隨手寫一個	Kruskal（好寫）
圖以鄰接矩陣給定	Prim 陣列版（天然契合）
圖以邊清單給定	Kruskal（天然契合）

★ 一個實用的記法：「圖怎麼給的，就用對應的演算法。」
鄰接矩陣 → Prim；邊清單 → Kruskal。

🧪 我實際套用的紀錄

• （待填）

⚠️ 注意 / 什麼時候不適用

• ★ 稠密圖不要用堆版。$O(V^2\log V)$ 比 $O(V^2)$ 慢，而且多了堆的配置與快取失誤。
• 只適用無向圖（同 Kruskal）。
• 圖不連通時 Prim 只會長出起點所在的那一棵——要偵測 minE[u] == INF 並回報。
  （Kruskal 天然會產生「最小生成森林」，Prim 不會。）
• INF 溢位：陣列版沒有累加所以較安全，但初始化仍要小心。
• 要記錄 MST 的邊（不只總權重）時，要額外維護 parent[v]。
• 負權沒問題（見上）。
• 邊權相同時 MST 不唯一，但總權重唯一。

🔗 相關工具

• Kruskal 最小生成樹 —— 另一種 MST 演算法、割性質的證明、以及怎麼選
• Dijkstra 最短路徑 —— 結構幾乎相同，差在「累不累加」
• 二元堆積 —— 稀疏圖版本的核心結構
• 貪婪演算法 —— 割性質
• 演算法導論