Algorithms on graphs

歡迎來到圖論演算法 (Algorithms on Graphs)！

在決策數學 1 (D1) 的這一章中，我們將學習如何使用「圖」(Graphs，即點與線構成的網絡) 來解決問題。你可以把它們想像成快遞司機的路線圖、網絡電纜佈局，甚至是社交媒體中的人際連接。

我們將重點探討兩個主要問題：
1. 最小生成樹 (Minimum Spanning Trees, MST)： 如何用最少的「材料」（如電纜或道路）連接網絡中的每一個點。
2. 最短路徑 (Shortest Path)： 如何以最快或成本最低的方式，從 A 點到達 B 點。

如果剛開始覺得這些概念有點抽象，別擔心！只要掌握了步驟，這其實就像跟著食譜做菜一樣簡單。

1. 最小生成樹 (Minimum Spanning Trees, MST)

想像你正在鋪設光纖電纜以連接五個村莊。你希望所有村莊都能接入網絡，但電纜很貴，所以你想使用最小總長度。這就是最小生成樹問題。

必須掌握的關鍵術語：

- 頂點 (Vertex / Node)： 圖中的一個點（例如：村莊）。
- 邊 (Edge / Arc)： 連接兩個頂點的線（例如：電纜）。
- 權重 (Weight)： 分配給每條邊的數字（例如：長度或成本）。
- 樹 (Tree)： 一個連通且沒有迴圈（沒有環路）的圖。
- 生成樹 (Spanning Tree)： 一棵包含圖中所有頂點的樹。

Kruskal 演算法 (Kruskal's Algorithm)

Kruskal 演算法是以「邊」為中心的演算法。它的邏輯非常簡單：只要不形成迴圈，就總是選擇成本最低的邊。

步驟：
1. 將圖中所有的邊按權重由小到大排列。
2. 檢查權重最小的邊。如果加入它不會產生迴圈（閉合環路），就選取它。
3. 接著看下一條權重最小的邊，重複上述步驟。
4. 當所有頂點都連通時停止（對於 \(n\) 個頂點的圖，你會得到 \(n-1\) 條邊）。

小撇步： 如果一條邊連接的兩個點已經可以透過其他已選取的邊互相到達，就捨棄它，因為加入它會形成迴圈！

Prim 演算法 (圖形版)

Prim 演算法是以「頂點」為中心的演算法。它像樹木一樣從起點開始向外生長。

步驟：
1. 隨便選一個頂點作為起點（題目通常會指定起點）。
2. 檢查所有與已選取頂點相連的邊。
3. 選擇連接到新頂點的最短邊。
4. 重複步驟，直到所有頂點都進入你的樹中。

類比： 想像一灘水從一個村莊開始流出，水流總是會沿著最短的路徑流向鄰近未濕的村莊。

Prim 演算法 (矩陣版)

有時候，題目會給出一張數字表（距離矩陣）。Pearson Edexcel 經常要求你直接在這張表上執行 Prim 演算法。

步驟：
1. 選擇一個起始頂點。將該頂點的欄位標記為「1」，並劃掉該頂點對應的列。
2. 查看已標記的欄位（即已在樹中的頂點所在的欄位）。
3. 在這些欄位中，找出一個未被劃掉的列中的最小數字。
4. 將該數字圈起來。該數字所在的列即為你的新頂點。
5. 將新頂點的欄位標記為下一個順序（2，然後是 3，以此類推），並劃掉其對應的列。
6. 重複此步驟，直到所有列都被劃掉。

常見錯誤： 忘記查看所有已標記的欄位。在尋找下一個最小值時，你必須檢查每一個頂部有編號的欄位！

MST 重點總結：

Kruskal 演算法需要先排序所有的邊。Prim 演算法則是一次增加一個頂點來構建樹。兩者最終都會得到相同的最小總權重！

2. Dijkstra 演算法 (最短路徑)

如果說 MST 是為了連接「所有人」，那麼 Dijkstra 演算法就是找出從特定起點到特定終點的最短路徑。這正是 Google 地圖或汽車導航計算路線的原理。

運作方式：

每個頂點都有一個「標籤框」。在 D1 中，這個框通常分為三部分：
1. 頂點名稱。
2. 標記順序（何時變為「永久」標籤）。
3. 最終（永久）標籤（從起點出發的最短距離）。

框內還有空間用於記錄臨時標籤（我們目前正在測試的距離）。

步驟流程：

1. 起點： 給起點賦予永久標籤 \(0\)。標記它是第 1 個被固定的頂點。
2. 更新： 查看所有與剛剛被設為永久的頂點直接相連的頂點。
3. 計算： 對於每個相鄰頂點，將該邊的權重加上你當前頂點的永久標籤值，寫入該鄰點的臨時標籤區。
4. 選擇： 觀察整個圖中所有的臨時標籤，找到最小的一個。
5. 永久化： 將該最小的臨時標籤變為永久，並標記其順序（第 2 個、第 3 個等）。
6. 重複： 以剛剛設為永久的頂點作為起點，回到第 2 步。繼續進行直到目標頂點獲得永久標籤為止。

你知道嗎？ Dijkstra 演算法是「貪婪」的。它總是選擇當下看起來最近的選項，相信這就是邁向最終目標的最佳步驟。

尋找實際路徑：

得到數字後，如何確定該走哪條路？你需要從終點倒推回去！

規則： 如果頂點 \(B\) 與頂點 \(A\) 相連，且：
\((\text{B 的永久標籤}) - (\text{邊 AB 的權重}) = (\text{A 的永久標籤})\)
...那麼邊 \(AB\) 就是最短路徑的一部分！

剛開始覺得複雜別擔心： 最重要的是保持整潔。如果你的「臨時標籤」寫得很亂，可能會選錯下一個永久標籤的數字。

速查表：

Dijkstra 演算法
- 起點： 標記 \(0\)。
- 計算： 將邊權重與當前的永久標籤相加。
- 選擇： 總是選取所有臨時標籤中的全局最小值作為下一個永久標籤。
- 回溯： 最後利用標籤來找出路徑。

3. 總結與成功秘訣

避免常見錯誤：

- 在 Kruskal 中： 不小心包含了一條會形成迴圈的邊。在加入新邊之前，務必再次檢查兩個點是否已經連通。
- 在 Prim (矩陣) 中： 忘記劃掉新頂點的列。這會導致你重複選取同一個已經造訪過的頂點。
- 在 Dijkstra 中： 忘記更新臨時標籤。如果你在過程中發現了某個頂點的更小臨時距離，一定要用新的、更小的數值取代舊的臨時標籤。

記憶法：

- Kruskal's Keeps edges in order (K 代表 Kruskal 和 Keep 排序)。
- Prim's Picks a starting vertex (P 代表 Prim's 和 Point 起始點)。
- Dijkstra is for Distance between two points (D 代表 Dijkstra 和 Distance 兩點間距離)。

本章要點：

圖論演算法是合乎邏輯的步驟流程。在考試中，評分員主要看你是否有清晰的步驟證據。務必展示 Kruskal 的排序列表、Prim 矩陣的標記順序，以及 Dijkstra 的所有臨時標籤。即使最終答案有輕微偏差，只要你展示了正確執行演算法的過程，依然可以拿到大部分分數！