Learning Objectives
- 說明生成樹與最小生成樹的定義，以及 n 個節點的生成樹剛好有 n - 1 條邊
- 用 parent 陣列實作 Union-Find 的 find 與 union，判斷兩個元素是否已經在同一組
- 說明路徑壓縮與依秩合併為什麼能讓樹保持很矮
- 追蹤 Kruskal 演算法：邊依權重排序，用 Union-Find 跳過會形成環的邊
- 說明 Prim 演算法從一個節點往外長的做法，並比較它和 Kruskal 的差別
用最少的線把每棟大樓連起來
學校要在五棟大樓之間鋪網路線。不是每兩棟之間都能拉線，能拉的路線各有不同的施工成本（萬元）：
| 路線 | A-B | A-C | B-C | B-D | C-D | D-E | C-E |
|---|---|---|---|---|---|---|---|
| 成本 | 4 | 3 | 1 | 2 | 2 | 5 | 6 |
要求是每兩棟大樓之間都要能連通（可以經過別棟轉接），而且總成本越低越好。
把大樓看成節點、路線看成有權重的邊，這就是一張圖（第 16 課）。符合要求的選法有兩個特徵：
- 連通：每個節點都接上了
- 沒有環：如果選出來的線繞成一圈，拿掉圈上任何一條，大家仍然連通，成本卻更低
連通又沒有環的子圖叫做生成樹（spanning tree）；所有生成樹裡總權重最小的，叫做最小生成樹（minimum spanning tree，MST）。 n 個節點的生成樹一定剛好有 n - 1 條邊：少一條就有節點接不上，多一條就一定會出現環。
這一課介紹兩個找最小生成樹的方法：Kruskal 演算法與 Prim 演算法。Kruskal 需要一個小工具，隨時回答「這兩個節點是不是已經連通了」，所以先從這個工具開始。
Union-Find：記錄誰和誰同一組
Union-Find（又叫併查集、disjoint set）管理「分組」：一開始每個元素自成一組，之後可以把兩組合併，也可以問兩個元素是不是同一組。
它把每一組存成一棵樹，只用一個陣列 parent：parent[x] 是 x 在樹上的上一層。根的 parent 是自己，根就是這一組的代表。
| 操作 | 做法 |
|---|---|
find(x) |
從 x 沿著 parent 一直往上走，走到根，回傳根 |
union(a, b) |
找出 a、b 各自的根；不同的話，把其中一個根的 parent 改成另一個根 |
| a、b 同一組嗎？ | find(a) == find(b) |
注意 union 不是把 b 掛到 a 底下，而是把兩組的根接起來；如果只改 parent[b]，b 原本那一組的其他成員就會被留在原地。
Union-Find 的 find 與 union
上方把 parent 陣列畫成森林：每一棵樹是一組，根在最上面。一開始 6 棵樹各只有一個節點。看最後一次 union(1, 3)：它先找出 1 的根 0、3 的根 2，再把 2 掛到 0 底下，兩組合成一組。在 find 裡面時，框起來的節點是 x 目前走到的位置。
讓樹保持很矮：路徑壓縮與依秩合併
find 的成本等於從 x 走到根的層數。如果合併的順序不好，樹可能長成一條長鏈，例如 5 → 4 → 3 → 2 → 1 → 0，
每次找 5 的根都要走 5 層，最壞情況是 O(n)，和線性搜尋一樣慢。有兩個常用的改良：
路徑壓縮（path compression）：find 找到根之後，順路把經過的每個節點直接掛到根上。下次再找它們，一步就到。
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x]) # 遞迴找到根，回來時把 parent[x] 改成根
return parent[x]
依秩合併（union by rank）：再多記一個陣列 rank，代表每棵樹高度的上限。合併時把矮的樹掛到高的樹底下，
這樣樹只有在兩棵一樣高時才會長高一層。
兩個一起用，每次操作的平均成本會小到幾乎是常數。Tarjan 在 1975 年證明了這個結果：m 次操作總共是 O(m·α(n))， α 是成長極慢的函數，在任何實際的資料量下都不超過 4。下面的範例先看路徑壓縮，依秩合併放在後面的 Kruskal 範例裡。
路徑壓縮：找一次，整條路都變短
一開始是一條 6 層的長鏈。第一次 find(5) 一路遞迴到根 0，回來的路上把 5、4、3、2 都直接掛到 0 底下，森林從一條長鏈變成一個根底下掛著五個子節點。第二次 find(5) 只呼叫了兩層。
想一想：Union-Find
下面的程式會印出什麼？
parent = [0, 0, 1, 1, 3, 5]
def find(x):
while parent[x] != x:
x = parent[x]
return x
print(find(4), find(5))
同樣的 parent = [0, 0, 1, 1, 3, 5]，用有路徑壓縮的遞迴 find(4) 之後，parent 變成什麼？
依秩合併「把矮的樹掛到高的樹底下」，主要的好處是什麼？
Kruskal 演算法：從最便宜的邊開始挑
Kruskal 在 1956 年發表了這個方法，想法非常直接：
- 把所有邊依權重由小到大排序
- 依序看每一條邊 (u, v)：如果 u 和 v 還不連通，就選這條邊，並把兩邊合併；如果已經連通，選了會形成環，跳過
- 選滿 n - 1 條邊就完成
「u 和 v 是否已經連通」正是 Union-Find 擅長的問題：find(u) == find(v) 就跳過，否則 union(u, v)。
為什麼每次挑最便宜、又不會成環的邊，最後的總和就是最小？直覺是：任何時候把節點分成兩群，橫跨兩群的邊裡最便宜的那一條， 一定可以放進某一棵最小生成樹（如果某棵最小生成樹沒用它，把它換進去、拿掉另一條橫跨兩群的邊，總成本不會變大）。 Kruskal 每次選的邊，都是它兩端所在的兩群之間最便宜的邊。下一課會再談這種「每一步選當下最好的」想法。
同樣權重時的順序：這張圖有兩條權重 2 的邊（B-D、C-D）。排序時權重相同再依 u、v 比較，三種語言才會選出同一棵樹。
Python 的元組 (權重, u, v) 排序時本來就依序比較每一個欄位；C++ 和 Java 要在比較函式裡寫清楚。
時間複雜度：排序 E 條邊是 O(E log E)，之後每條邊兩次 find，幾乎是常數，所以整體是 O(E log E)。
Kruskal：排序、挑邊、跳過會成環的邊
圖的面板用粗線標出已經選的邊，另一個面板是 Union-Find 的森林。B-C、B-D 選進來之後，B、C、D 已經在同一棵樹裡，所以 C-D 被跳過；A-B 也一樣。選滿 4 條邊（5 個節點）就停，總成本 11，最後的 C-E 不必再看。
Prim 演算法：從一個節點往外長
另一個常用的方法是 Prim 演算法。Prim 在 1957 年發表，處理的正是電話網路的連線成本； 後來大家發現捷克數學家 Jarník 在 1930 年就提出過同樣的方法，所以也叫 Jarník–Prim 演算法。
Kruskal 是在整張圖裡到處挑便宜的邊，同時長出好幾棵小樹，最後才接成一棵。Prim 則從一個起點開始，只維護一棵樹：
- 起點的成本設成 0，其他節點設成 ∞
- 從還沒進樹的節點裡，挑「接到樹上最便宜」的節點 u，把它加進樹
- 看 u 的每個鄰居 v：如果邊 u-v 比 v 目前記錄的成本便宜，就更新成這條邊
- 重複 2、3，直到所有節點都進樹
這個步驟和第 18 課的 Dijkstra 幾乎一樣，差別只在第 3 步比的東西：Dijkstra 比的是「從起點到 v 的總距離」，Prim 比的是「單一條邊 u-v 的權重」。 下面的範例每一輪掃過所有節點找最小值，是 O(n²) 的寫法，適合邊很多的圖；邊比較少時，可以像 Dijkstra 一樣用優先佇列，變成 O(E log n)。
Prim：一次加入一個最便宜的節點
節點上方的數字是 dist：這個節點目前接到樹上最便宜的成本，還接不到的顯示 ∞。程式裡節點用編號 0～4 代表 A～E。從 A 開始，依序加入 C、B、D、E。注意它選的是 C-D 而不是 Kruskal 選的 B-D：兩條都是 2，所以兩棵樹的總成本一樣是 11。
Kruskal 和 Prim 怎麼選
| Kruskal | Prim | |
|---|---|---|
| 一次處理 | 一條邊（全圖最便宜、不成環的） | 一個節點（最便宜接到樹上的） |
| 需要的工具 | 排序＋Union-Find | 陣列掃描或優先佇列 |
| 時間複雜度 | O(E log E) | O(n²)；用優先佇列是 O(E log n) |
| 適合 | 邊比較少的圖、邊本來就存成一張清單 | 邊很多的圖、用鄰接矩陣存的圖 |
兩個演算法都保證得到最小的總成本。範例圖的兩條權重 2 的邊讓兩者選出不同的樹，這說明最小生成樹不一定只有一棵； 所有邊的權重都不相同時，最小生成樹才保證唯一。
最小生成樹也常用在分群：先建出最小生成樹，再拿掉最貴的 k - 1 條邊，剩下的 k 塊就是一種分成 k 群的方法，群和群之間的距離盡量大。
想一想：最小生成樹
一張連通的圖有 8 個節點、15 條邊，它的最小生成樹有幾條邊？
Kruskal 看到一條邊 (u, v)，發現 find(u) == find(v)，為什麼要跳過它？
範例圖上 Kruskal 選了 B-D，Prim 選了 C-D。哪個說法正確？
Kruskal 演算法的時間主要花在哪裡？
實作：7 個節點的最小生成樹
find 和 union 已經寫好了。請把邊排序，依序檢查每一條邊，能合併就選它，印出 A-D 5 這樣的一行，最後印出總成本。權重相同時依 u、v 排序，輸出才會和右邊的預期輸出一樣。
重點整理
- 生成樹：連通、沒有環，n 個節點剛好 n - 1 條邊；最小生成樹是總權重最小的生成樹，可能不只一棵
- Union-Find：
parent陣列把每一組存成一棵樹，find找根，union把兩個根接起來 - 路徑壓縮讓 find 經過的節點直接掛到根上；依秩合併把矮的樹掛到高的樹底下；兩者一起用，每次操作幾乎是常數
- Kruskal：邊依權重排序，用 Union-Find 跳過會成環的邊，O(E log E)
- Prim：從一個節點往外長，每次加入接到樹上最便宜的節點，O(n²) 或用優先佇列 O(E log n)
下一課：貪婪演算法。Kruskal 和 Prim 每一步都選「當下最便宜」的，這種策略叫做貪婪；下一課看它什麼時候行得通、什麼時候會失敗。