用最少的總成本,把所有點連起來、不留多餘的線。兩個貪婪法,殊途同歸。
1. 所有邊由小排到大 —— 先把整張圖的邊照權重排序。
2. 一條一條收,成環就丟 —— 從最便宜的看起:若這條邊的兩端還沒連通就收下;若已經連通(收了會繞圈)就跳過。
3. 用並查集判「有沒有連通」 —— 兩端 find 出來同一個根 = 已連通 = 會成環;不同根就 union 合併、收這條邊。
4. 收滿 V−1 條就完成 —— 過程中圖上可能同時有好幾塊分開的森林,Kruskal 不管連不連,只挑當下最便宜的,最後自然併成一棵。
1. 從任一點開始當「樹」 —— 挑個起點,樹裡先只有它一個。
2. 每次接最便宜的「跨界邊」 —— 在所有「一端在樹裡、一端在樹外」的邊裡,挑權重最小的收下,把外面那個點拉進樹。
3. 用最小堆挑最便宜 —— 拿優先佇列存候選的跨界邊,每次 pop 最小的(跟 Dijkstra 幾乎同一套骨架)。
4. 全程只有一塊連通的樹 —— 跟 Kruskal 不同,Prim 的樹從頭到尾都連在一起,一路往外長到涵蓋所有點。
O(1)。log。O(E log V) 通常較划算(尤其用更進階的堆)。兩者答案一樣,只差效率。要把幾個村莊都接上電、又想省最多電線,那組最省的接法就是 MST。
用最少的總里程,把所有城鎮連成一個路網,不修多餘的重複路段。
機房之間拉光纖,總成本最低又保證全部連通 —— 骨幹就是一棵 MST。
同一張加權圖,兩種蓋法。Kruskal 全域挑最便宜的邊(會先冒出幾塊分開的森林再併起來),成環的邊丟掉(紅色虛線);Prim 從節點 0 開始,一整塊往外長。已收進 MST 的邊是綠色粗線、正在看的是紫色。兩者最後都得到總權重 18 的同一棵樹。按「下一步」。
從 Kruskal(排序 + 並查集)、判環引擎、Prim(heapq),到還原 MST 邊、切割性質、Kruskal vs Prim、最大生成樹、判連通,最後應用與小結。
❌ 圖不連通還硬求 MST —— 生成樹要連通所有點;若圖本身分成好幾塊,根本沒有生成樹。用「收到的邊數是否等於 V−1」判斷(不滿就是不連通)。
❌ Kruskal 不判環 / 判環寫錯 —— 一定要用並查集檢查兩端是否已連通,否則會收成環、變不出樹。
❌ Prim 忘了跳過「已在樹裡」的點 —— 優先佇列裡會有指向已收節點的過期邊,pop 到時要用 if intree[v]: continue 跳過。
❌ 以為 MST 唯一 —— 邊權有重複時,MST 可能不只一棵(但總權重都一樣)。權重全相異才保證唯一。
把答案打到對話裡,我幫你對。