Algorithms on graphs

歡迎來到圖算法（Graph Algorithms）的世界！

在決策數學 1 (Decision Mathematics 1, D1) 的這一章中，我們將學習如何利用圖（Graphs）（即網絡）來解決現實世界中的問題。想像你是一位工程師，需要用最少的材料將多個城鎮連接起來；或者你是一位送貨司機，正在尋找兩座城市之間絕對最短的路線。這些絕非猜謎遊戲——我們使用稱為算法（Algorithms）的特定、分步驟的規則，來確保每次都能找到完美的答案。

如果起初覺得這些概念有點抽象，請不用擔心。我們會將所有內容拆解成簡單的步驟，使用你熟悉的類比，並指出學生常犯的「陷阱」。讓我們開始吧！

1. 最小生成樹（「最小連接」問題）

想像你有一組島嶼，你想用橋樑將它們連接起來。為了節省成本，你希望橋樑的總長度最小，但必須確保每個島嶼都能連接到網絡中。這就是所謂的最小生成樹 (Minimum Spanning Tree, MST)。

你需要了解的關鍵術語：
• 頂點 (Vertex / Node)： 圖上的一個點（例如城鎮或島嶼）。
• 邊 (Edge / Arc)： 連接兩個頂點的線段。
• 權重 (Weight)： 邊上的數值（代表距離、成本或時間）。
• 樹 (Tree)： 一個連通且沒有圈（即沒有迴路）的圖。
• 生成樹 (Spanning Tree)： 一棵連接圖中所有頂點的樹。

尋找 MST 有兩種主要算法：庫斯克爾算法 (Kruskal’s Algorithm) 和 普林算法 (Prim’s Algorithm)。

庫斯克爾算法 (Kruskal’s Algorithm)

Kruskal 算法就像是一位精打細算的獵人。只要不形成迴路，你總是優先選擇最便宜的「交易」（邊）。

操作步驟：
1. 將圖中所有的邊按大小（從小到大）列出。
2. 從整個圖中最短的邊開始；將它加入你的樹中。
3. 選擇下一條最短的邊。將它加入，除非它會形成一個圈（cycle）（即閉合迴路）。如果會形成迴路，就把它捨棄！
4. 重複上述步驟直到所有頂點都連接起來。對於有 \(n\) 個頂點的圖，你將需要剛好 \(n - 1\) 條邊。

避免常見錯誤： 學生經常忘記檢查是否有圈。請務必問自己：「如果我加上這條邊，我能繞成一個圈嗎？」如果答案是肯定的，就不要加上那條邊！

普林算法 (Prim’s Algorithm)

Prim 算法則不同，它像樹木一樣從一個起點開始「生長」。你總是尋找離你當前網絡最近的鄰居。

操作步驟（在圖上）：
1. 選擇任意一個頂點作為起點（通常題目會指定）。
2. 查看所有連接「已開始」頂點和「未開始」頂點的邊。選擇其中最短的一條。
3. 將該新頂點加入你的集合。現在，檢查所有連接你已連接的頂點到新頂點的邊。
4. 重複直到所有頂點都被包含在內。

在距離矩陣（Distance Matrix）上使用 Prim 算法：
在考試中，你經常會被要求使用表格（矩陣）來執行 Prim 算法。這是 Pearson Edexcel 課程大綱中非常常見的要求。
1. 選擇一個起始頂點，並在其對應列的上方標記為 "1"。
2. 劃掉該頂點的行。
3. 查看已標記列中的數值（例如第 1 列）。圈出最小的可用數值。
4. 該數值所對應的行所代表的頂點，就是你的下一個頂點。將其列標記為 "2"，劃掉其行，然後重複步驟。

快速複習箱：
• Kruskal 算法： 從全圖最短邊開始。順序不重要，但嚴禁形成迴路。
• Prim 算法： 從一個頂點開始。從已連接的網絡中逐步擴展。

2. 戴克斯特拉算法 (Dijkstra’s Algorithm)（最短路徑）

雖然 MST 是為了以最低成本連接所有人，但 Dijkstra 算法是用於尋找從一個特定起點到另一個特定目的地之間的最短路徑。可以把它想作是 GPS 或 Google 地圖背後的邏輯。

工作框（Working Box）：
在考試中，你會在每個頂點看到一個「框」。它看起來像這樣：
\( [ \text{標記順序} \mid \text{最終標籤} \mid \text{運算數值} ] \)

操作步驟：
1. 開始： 將起始頂點的最終標籤設為 0。標記順序為 1。
2. 更新： 查看所有與你剛設為「永久」的頂點相連的頂點。計算從起點到這些鄰居的距離。將結果寫在「運算數值」部分。
3. 選擇： 查看整張圖上所有臨時運算數值。選出最小的一個。這就是你的新「永久」頂點。
4. 定案： 為它分配下一個「標記順序」及其「最終標籤」（距離）。
5. 重複： 繼續進行，直到目的地頂點獲得最終標籤。

類比： 想像水從起點開始淹沒迷宮。「最終標籤」就是水第一次到達該特定交叉口的時間。

如何找出實際路徑：
一旦獲得最終標籤，請從目的地倒著推回去。如果符合以下條件，則頂點 \(B\) 在從 \(A\) 到目的地的路徑上：
\( (\text{B 的最終標籤}) - (\text{A 的最終標籤}) = \text{邊 } AB \text{ 的權重} \)

避免常見錯誤： 在選擇下一個永久頂點時，必須查看整張圖上所有的臨時標籤，而不僅僅是當前頂點旁邊的標籤！

總結與重點提示

你知道嗎？
「最小連接」問題最初是由科學家在 1920 年代試圖設計高效電力網時解決的。今天，同樣的數學原理被 Netflix 等公司使用，以確保數據能快速傳送到你的屏幕上！

期末複習：
• 如果你有一份所有邊的列表並且想避免形成迴路，請使用 Kruskal 算法。
• 如果你從特定頂點開始，或者正在處理矩陣/表格，請使用 Prim 算法。
• 如果你需要找出從 A 點到 B 點的最短路徑，請使用 Dijkstra 算法。
• 在 Dijkstra 算法中，務必顯示你的運算數值——即使你把它們劃掉了。考官需要看到你在紙上的「思考過程」！

如果起初覺得這些很棘手，請別擔心！ 掌握這些算法的最佳方法就是練習繪製圖表並填寫表格。一旦你找到了步驟的節奏，這就變成了一個你每次都能完美解開的謎題。