歡迎來到圖論演算法！
在決策數學 1 (Decision Mathematics 1) 的這一章中，我們將從圖論的基本定義邁向精彩的演算法 (algorithms) 世界。演算法本質上就是用來解決特定問題的一步步指令。
為什麼這很重要？因為無論是你使用 GPS 規劃回家最快的路徑，還是公司試圖以最少材料鋪設光纖電纜，背後使用的正是這些數學工具！
如果起初覺得步驟很多，不用擔心——把它們想像成食譜就好。只要按順序執行這些步驟，你每次都能得到正確的結果。
1. 最小生成樹 (Minimum Spanning Trees, MST)
想像你要將多個住戶連接到主水管。你希望每個住戶都能接通，但為了節省開支，你想使用總長度最短的管線。這就是最小生成樹問題。
生成樹 (Spanning Tree) 是一個子圖，它包含了原圖中的每一個頂點 (vertex)，但沒有迴路 (cycle)（它看起來像一棵「樹」）。而最小生成樹就是所有邊的權重總和為最小的那一個。
克魯斯克爾演算法 (Kruskal’s Algorithm)
這是一種「貪婪 (greedy)」的方法。你只需尋找當前可選的最短邊即可。
步驟：
1. 將圖中所有的邊按權重由小到大排列。
2. 選擇權重最小的邊。
3. 選擇下一條最便宜的邊。關鍵規則：如果加入這條邊會形成迴路，就跳過它！
4. 重複上述步驟，直到所有頂點都連通為止（對於 \(n\) 個頂點，你最後會有 \(n-1\) 條邊）。
普林演算法 (Prim’s Algorithm) - 圖形版
普林演算法與前者不同，它像植物生長根系一樣，從起點開始擴展生成樹。
步驟：
1. 從任何一個頂點開始。
2. 查看所有連接「已選頂點」到「未選頂點」的邊。
3. 選擇權重最短的那條邊。
4. 重複步驟直到所有頂點都被包含在內。
普林演算法 (Prim’s Algorithm) - 矩陣版
在考試中，你經常被要求使用距離矩陣 (distance matrix) 來執行普林演算法。它看起來很嚇人，但實際上非常有規律！
步驟：
1. 選擇一個起始頂點（通常為 A），並在其欄位上方標記「1」。劃掉 A 行。
2. 查看所有已標記欄位中的數值。
3. 在這些欄位中圈出最小值（忽略你已經劃掉的行）。
4. 該圈選值所在的行即為下一個頂點。為其欄位標記下一個數字（例如「2」），並劃掉該行。
5. 重複直到所有欄位都被標記為止。
常見錯誤：忘記劃掉剛加入的頂點所在的行。如果不劃掉它，你可能會不小心選到一條回到「已選頂點」的邊！
重點總結：克魯斯克爾演算法先對所有邊進行排序；普林演算法則是一次增加一個連通頂點來構建樹。
2. 尋找最短路徑
這是課程中關於「Google 地圖」的部分。我們的目標是找出特定起點與終點之間的最短距離。
戴克斯特拉演算法 (Dijkstra’s Algorithm)
此演算法可找出從一個起點到網絡中所有其他頂點的最短路徑。
步驟：
1. 給起點一個永久標籤 (permanent label) 0。
2. 對於每個連接到當前節點的節點，計算一個工作值 (working value)（到當前節點的距離 + 邊的權重）。
3. 如果這個新值比之前的任何工作值小，就替換掉它。
4. 查看整個圖中所有的工作值，選擇最小的一個——這就成為該點的永久標籤。
5. 從這個新的永久節點重複上述步驟，直到終點有了永久標籤為止。
記憶小撇步：將戴克斯特拉演算法想像成水從起點向外氾濫。永久標籤告訴你「水」第一次到達該點的確切時間。
弗洛伊德演算法 (Floyd’s Algorithm)
戴克斯特拉演算法從一點出發，而弗洛伊德演算法則找出圖中每一對頂點之間的最短路徑。它使用兩個矩陣：距離矩陣 (Distance Matrix) 和路徑矩陣 (Route Matrix)。
過程：
對於一個擁有 \(n\) 個頂點的圖，你需要進行 \(n\) 次迭代。
在第 1 次迭代中，你使用頂點 1 作為「樞紐 (pivot)」。檢查經由頂點 1 從 \(A\) 到 \(B\) 是否比當前從 \(A\) 到 \(B\) 的直接距離更短。
如果 \(Dist(A, 1) + Dist(1, B) < Dist(A, B)\)，則用新的較短距離更新矩陣。
快速回顧：戴克斯特拉適合「一對多」；弗洛伊德適合「多對多」。
3. 路線檢查演算法 (Route Inspection Algorithm)
又稱為中國郵差問題 (Chinese Postman Problem)。目標是走過每一條邊至少一次並回到起點，同時使總距離最小化。
「奇數節點」的概念：
如果一個圖的所有頂點度數（連接邊的數量）均為偶數，該圖即為歐拉圖 (Eulerian)。你可以完美地遍歷它。
如果圖中有奇數節點，你必須重複走過某些邊。在 Edexcel 教學大綱中，你將處理擁有最多四個奇數節點的網絡。
步驟：
1. 找出所有的奇數頂點。
2. 列出這些奇數頂點的所有可能配對方式。
3. 找出每對之間的最短路徑（必要時使用戴克斯特拉演算法）。
4. 選擇總權重最小的配對方式。
5. 將這些重複邊的權重加到圖的總權重中。
你知道嗎？如果只有兩個奇數節點，只需找出它們之間的最短路徑並重複即可，很簡單！
4. 旅行推銷員問題 (Traveling Salesman Problem, TSP)
TSP 與路線檢查不同。這裡的目標是造訪每一個頂點一次並回到起點，同時使距離最小化。這類問題很難完美解決，因此我們尋找界限 (Bounds)。
上界 (Upper Bounds，即「足夠好」的路線)
上界是我們知道可以達到的距離，即使它不一定是絕對最好的。
1. 最近鄰居演算法 (Nearest Neighbour Algorithm)：從一個頂點開始，前往最近的未造訪頂點。重複直到所有點都被造訪，最後回到起點。
2. 雙倍最小生成樹 (Double MST)：找出 MST，然後將其邊加倍（對每一條邊來回走一次）。這總是一個有效的路徑，但通常比較長。
下界 (Lower Bounds，即「不可能比這更好」的數值)
下界是一個理論最小值，你可能實際上無法達到它。
刪除頂點法 (Deleted Vertex Method)：
1. 刪除一個頂點及其所有連接的邊。
2. 找出剩餘頂點的最小生成樹 (MST)。
3. 加上與被刪除頂點相連的兩條最短邊的權重。
4. 結果即為下界。若要找到最佳下界，請針對不同的刪除頂點重複此步驟，並選取最大的數值。
重點總結：實際的最優解位於你的最大下界 (Highest Lower Bound) 和最小上界 (Lowest Upper Bound) 之間。
總結檢查清單
- MST：克魯斯克爾（針對邊）或普林（針對頂點/矩陣）。
- 最短路徑：戴克斯特拉（單一起點）或弗洛伊德（所有起點）。
- 每一條邊：路線檢查（配對奇數節點）。
- 每一個頂點：TSP（上界 = 最近鄰居；下界 = 刪除頂點 + MST）。
如果剛開始覺得很難，不用擔心！學習演算法最好的方法就是拿一張紙，畫一個小網絡，然後親自動手執行步驟。你一定可以的！