歡迎來到圖論演算法！

在本章中，我們將探索決策數學（Decision Mathematics）中最實用的工具。如果你曾經好奇 Google 地圖是如何找出最快的回家路線，或是公司如何設計纜線網絡以節省最多的材料，現在你即將揭開這些謎底！

決策數學的核心就是效率——在節省時間、金錢或資源的同時，找出處理問題的最佳方案。別擔心，這些演算法初看之下步驟繁瑣，但它們其實只是一套我們必須遵守的邏輯「食譜」。讓我們開始吧！

1. 基礎概念：什麼是圖 (Graph)？

在進入演算法之前，我們必須先掌握基礎術語。在決策數學中，圖 (Graph) 並非 x-y 軸上的曲線，而是一系列點與線的集合。

關鍵術語：
• 頂點 (Vertices 或 Nodes)： 圖上的點。
• 邊 (Edges 或 Arcs)： 連接頂點的線。
• 權重 (Weight)： 標註在邊上的數值（代表距離、成本或時間）。
• 網絡 (Network)： 每條邊都有權重的圖。
• 路徑 (Path)： 一連串的邊，且過程中不會經過同一個頂點兩次。
• 環 (Cycle)： 起點與終點為同一個頂點的路徑（即封閉迴路）。
• 樹 (Tree)： 一個連通且沒有環的圖。
• 生成樹 (Spanning Tree)： 一棵連接圖中所有頂點的樹。

快速回顧： 試著將「樹」想像成家族樹（家譜）——無論你向下追溯多遠，都不會繞圈回到原點！

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

想像你是電訊工程師，需要連接 5 個城市並鋪設光纖。你希望所有城市都能連接到網絡，但總鋪設成本（纜線長度）必須最低。這就是最小生成樹問題。

我們主要使用兩種演算法來解決：古魯斯克演算法 (Kruskal’s Algorithm) 與 普林演算法 (Prim’s Algorithm)。

古魯斯克演算法 (Kruskal’s Algorithm)

這是一種「貪婪」演算法。它單純地從整個網絡中尋找最短的邊，而不考慮它們的位置。

逐步教學：
1. 將網絡中所有的邊按權重由小到大排列。
2. 選取最短的邊，將其加入你的 MST。
3. 選取下一條最短的邊。僅在不會產生環（封閉迴路）的情況下將其加入。
4. 重複上述步驟，直到所有頂點都連通。若有 \(n\) 個頂點，你將剛好需要 \(n-1\) 條邊。

常見錯誤： 同學們常忘記檢查是否會產生「環」！務必問自己：「如果我加入這條邊，會不會形成一個圈？」如果答案是肯定的，就跳過這條邊！

普林演算法 (Prim’s Algorithm，適用於網絡圖)

普林演算法像是一種「生長」演算法。它從一個頂點開始，像藤蔓一樣向最近的鄰居延伸。

逐步教學：
1. 隨意挑選一個起點頂點。
2. 檢查所有連接「已選頂點」與「未選頂點」的邊。
3. 挑選權重最小的邊並將其加入。
4. 重複步驟直到所有頂點都進入樹中。

你知道嗎？ 與 Kruskal’s 不同，Prim’s 演算法天生就能避免產生環，因為你始終是將一個「新」頂點連接到「已選」的群組中。

普林演算法 (使用矩陣)

有時網絡會以表格（距離矩陣）形式提供，而非圖形。課程大綱明確要求你必須掌握這種操作方法。

逐步教學：
1. 選擇一個起點頂點（通常是第一列），並刪除該列。將該頂點的欄位標記為「1」。
2. 檢視所有已標記（例如「1」）欄位中的數字。
3. 找出這些欄位中的最小值。該值所在的列即為下一個要加入的頂點。
4. 寫下該邊及其權重。刪除該新頂點所在的列，並將其欄位標記為下一個數字（例如「2」）。
5. 重複步驟直到所有列都被刪除。

關鍵總結： Kruskal’s 是在圖上各處零散地建立樹的片段，而 Prim’s 則是從一點出發，建立一個不斷長大的單一樹狀結構。

3. 戴克斯特拉演算法 (Dijkstra’s Algorithm，最短路徑)

Dijkstra’s 演算法用於尋找從單一起點到終點的最短路徑。這正是衛星導航的運作原理！

我們在頂點上使用特殊的標記系統。每個頂點都有一個三部分的標籤格：
1. 標記順序： 該頂點何時被設為「永久」？
2. 最終（永久）標籤： 從起點到該處的最短實際距離。
3. 工作數值： 當我們發現更好的路徑時，會更新這些暫時的距離。

逐步教學：
1. 將起點頂點的永久標籤設為 0，標記順序為 1。
2. 更新： 針對剛設為永久的頂點，檢查其所有連接的鄰居。計算到它們的距離（當前節點距離 + 邊權重）。
3. 將結果寫為該鄰居的工作數值。如果該處已有數值，只有在取得更小數值時才進行替換。
4. 選擇： 檢視整個圖中所有工作數值。挑選出最小的一個，使其成為下一個永久標籤。
5. 重複直到你的終點頂點被設為永久為止。

別擔心，初學時可能會覺得很複雜！ 只要記住黃金法則：在檢查過所有其他可能到達的路徑前，絕對不要將工作數值設為永久。整個圖中最小的工作數值永遠是你的下一個選擇目標。

找出路徑： 完成後，如何確認該走哪條路？從終點往回推！若滿足以下條件，則該頂點位於最短路徑上：
\( (頂點 \ B \ 的數值) - (頂點 \ A \ 的數值) = 邊 \ AB \ 的權重 \)

快速回顧：
• Kruskal/Prim： 用於連接所有人並取得最低總成本。
• Dijkstra： 用於連接某兩點以取得單程最短路徑。

4. 關鍵技能總結

要掌握這一章，你需要具備以下能力：
• 說明路徑 (path) 與 環 (cycle) 的區別。
• 透過邊的排序並避開環來執行 Kruskal’s 演算法。
• 在圖形上執行 Prim’s 演算法，總是選擇離現有樹最近的「鄰居」。
• 在矩陣上執行 Prim’s 演算法，透過標記欄位與刪除列來完成。
• 使用「標籤格」方法執行 Dijkstra’s 演算法，以找出兩點間的最短路徑。

最後提示： 在考試中執行這些演算法時，請務必寫下每個步驟！即使最終答案正確，評分標準通常也會包含邊的排序列表（Kruskal’s）或是標籤格中的工作數值更新過程（Dijkstra’s）。