🧠 進階演算法：圖論演算法 (9645)
你好！歡迎來到電腦科學中最強大也最令人興奮的課題之一：圖論演算法 (Graph Algorithms)。圖 (Graph) 不僅僅是長條圖——它們是基本的數據結構，用於模擬現實世界中複雜的關係，從社交網絡到互聯網的地圖繪製，無處不在。
掌握這些演算法意味著你可以找出回家的最快路徑、解決謎題，並理解現代軟體如何處理互聯數據。如果這看起來有點複雜，別擔心；我們會將每個概念拆解，並使用清晰的類比，幫助你輕鬆理解！
1. 圖論基礎：定義結構
在我們對圖執行演算法之前，我們需要了解圖究竟是什麼以及它是如何構建的。
1.1 核心術語 (3.10.1)
圖 (Graph) 是一種用於表示數據之間複雜關係的數據結構。
- 頂點 (Vertex) 或 節點 (Node)：表示關係中的一個實體或點。（想像成地圖上的一個城市或社交網絡中的一個人。）
- 邊 (Edge) 或 弧 (Arc)：表示兩個頂點之間的連接或關係。（想像成連接兩個城市的道路。）
圖的類型
我們使用的演算法類型通常取決於我們處理的圖的類型：
- 無向圖 (Undirected Graph)：邊沒有方向。如果節點 A 連接到節點 B，這種連接是雙向的。（雙向行車道。）
- 有向圖 (Directed Graph)：邊有特定的方向（弧）。關係只有單向。（單行道，或者 Twitter 上的追蹤關係：我追蹤你，但你不一定追蹤我。）
- 加權圖 (Weighted Graph)：每條邊都有一個相關聯的數值（「權重」）。這個值通常代表成本、距離或時間。（道路長度或航班票價。）
快速回顧： 圖論演算法通常專注於在節點之間尋找路徑，或者有系統地拜訪所有節點。
1.2 在程式碼中表示圖 (3.10.1)
在記憶體中，圖通常使用兩種主要結構來儲存：
a) 鄰接矩陣 (Adjacency Matrix)
這使用二維陣列（矩陣），其中行和列代表節點。如果節點 \(i\) 和節點 \(j\) 之間存在邊，則單元格 \([i][j]\) 會被標記（對於無權圖通常標記為 1，對於加權圖則填入權重值）。
- 優點（何時使用矩陣）：
- 容易測試邊是否存在（檢查 \([i][j] = 1\) 是否成立）。這被稱為頻繁檢查邊的存在/缺失。
- 可以快速添加/刪除邊。
- 最適合稠密圖 (Dense Graphs)（相對於頂點數量而言，邊很多的圖）。
- 缺點：對於稀疏圖 (Sparse Graphs)（邊很少的圖）來說，會浪費記憶體，因為大部分的矩陣條目都是零。
b) 鄰接串列 (Adjacency List)
這使用列表或陣列，每個索引代表一個節點。在每個索引處，有一個鏈結串列（或陣列/列表）包含該節點的所有鄰居。
- 優點（何時使用串列）：
- 對於稀疏圖來說，記憶體使用效率更高，因為你只儲存現有的連接。
- 尋找特定節點的所有鄰居速度更快。
- 缺點：檢查是否存在特定的邊（從 A 到 B）需要遍歷 A 的整個鄰居列表，這可能比直接矩陣查詢慢。
第 1 部分重點總結： 圖通過邊 (Edges) 連接節點 (Vertices)。我們使用鄰接矩陣進行快速的邊檢查並處理稠密圖，而對於稀疏圖，則使用鄰接串列以節省記憶體。
2. 搜尋演算法：廣度優先搜尋 (BFS) (3.11.1)
搜尋演算法用於有系統地探索圖。BFS 就像把石頭扔進池塘——漣漪層層向外擴散。
2.1 什麼是廣度優先搜尋 (BFS)？
BFS 按層級（即「廣度」）探索圖。它會先找到起始節點的所有鄰居，然後再找到鄰居的鄰居，以此類推，直到深入圖的內部。
記憶小撇步： Breadth-First（廣度優先）使用 Broad（廣泛）的方法，並使用 Queue（隊列，FIFO 先進先出）。
核心數據結構： BFS 使用一個隊列 (Queue) 來管理下一個要拜訪的節點。這確保了離起點越近的節點會越先被拜訪。
2.2 BFS 演算法執行步驟
- 從指定的起始節點開始。將其標記為已拜訪並加入到隊列中。
- 當隊列不為空時：
a. 取出 (Dequeue) 第一個節點，稱為當前節點。
b. 檢查當前節點所有未拜訪的鄰居。
c. 對於每個未拜訪的鄰居，將其標記為已拜訪並加入 (Enqueue) 到隊列中。 - 重複直到隊列為空。
你知道嗎？ 因為 BFS 會在轉向距離 \(d+1\) 之前，有系統地檢查所有距離為 \(d\) 的節點，所以它本質上能找到無權圖中的最短路徑。這是你需要掌握的主要應用！
2.3 BFS 的應用 (3.11.1)
BFS 的典型應用是尋找無權圖的最短路徑。由於所有邊的「權重」相同（為 1 單位），該演算法保證你第一次到達目的地節點時，所經過的邊數是最少的。
例如：尋找社交網絡中兩個人之間最少的連接數。
BFS 重點總結： BFS 使用隊列，按層級進行探索，是尋找無權圖最短路徑的最佳選擇。
3. 搜尋演算法：深度優先搜尋 (DFS) (3.11.1)
DFS 就像一位冒險家，一旦選定路徑，就會勇往直前，盡可能深入，直到無路可走才回溯。
3.1 什麼是深度優先搜尋 (DFS)？
DFS 沿著圖中的單一分支或路徑探索，直到觸及死胡同（沒有未拜訪鄰居的節點）。然後，它會「回溯」到上一個分岔路口，嘗試下一條路徑。
類比： 探索迷宮。你沿著一條通道一直走直到撞牆，然後回到上一個轉角處嘗試下一條通道。
核心數據結構： DFS 使用堆疊 (Stack)（後進先出）或遞迴 (Recursion)（利用呼叫堆疊）來管理回溯時返回的路徑。
3.2 DFS 演算法執行步驟
- 從指定的起始節點開始。將其標記為已拜訪並處理它。
- 如果當前節點有未拜訪的鄰居：
a. 選擇一個未拜訪的鄰居，將其設為新的當前節點。（這實際上是遞迴呼叫或將節點推入堆疊的操作）。 - 如果當前節點沒有未拜訪的鄰居（死胡同）：
a. 回溯 (Backtrack) 回到前一個節點，並嘗試從該點開始的其他剩餘未拜訪鄰居。 - 重複直到所有可觸及的節點都已拜訪完畢。
實作： 你必須能夠在程式中實作 BFS 和 DFS。在考試場景中，DFS 通常使用遞迴子程序來實作最為簡單。
3.3 DFS 的應用 (3.11.1)
DFS 的典型應用是迷宮導航或解決謎題，你需要徹底探索一個選項後才放棄。
例如：確定兩點之間是否存在路徑，或進行拓撲排序（根據依賴關係排列任務）。
DFS 重點總結： DFS 使用堆疊（或遞迴），在回溯前深入探索單一路徑，適用於迷宮導航和路徑存在性檢查。
4. 最短路徑演算法：戴克斯特拉演算法 (Dijkstra's Algorithm) (3.11.1)
BFS 對於無權圖效果很好。但如果道路有不同的距離或成本呢？這時我們就需要戴克斯特拉演算法。
4.1 戴克斯特拉演算法的目的
戴克斯特拉演算法用於找出加權圖中，起始節點與所有其他節點之間的最短路徑，前提是邊的權重必須是非負數（不能有負距離或負時間）。
類比： 這正是你的 GPS 在計算兩點之間最快路線時所做的工作——它考慮了每條道路（邊）的權重（距離/時間）。
4.2 演算法追蹤（重點在於理解）
除非題目給出步驟，否則你不需要背誦完整步驟或編寫程式碼，但你必須具備追蹤 (Trace) 的能力。
追蹤的核心概念是維護兩組關鍵數據：
- 距離 (Distances)：記錄從起始節點到每個其他節點的最短已知距離。最初，起始節點的距離為 0，其餘皆設為無窮大 (\(\infty\))。
- 已拜訪集合 (Visited Set)：已確定從源點出發的最短距離的節點集合。
追蹤過程（簡化版）
- 初始化距離列表（起點 = 0，其餘 = \(\infty\)）。
- 選擇未拜訪節點中距離最小的一個（首次選擇即為起點）。
- 將該節點標記為已拜訪（它的最短路徑現在已定案）。
- 對於已拜訪節點的所有鄰居，計算暫定距離（當前節點距離 + 邊權重）。
- 如果這個暫定距離小於該鄰居當前記錄的距離，則更新為更小的值。（這個過程稱為鬆弛 (Relaxation)）。
- 重複步驟 2-5，直到目標節點被拜訪，或所有可觸及節點皆已加入已拜訪集合。
常見錯誤： 戴克斯特拉演算法只有在權重為非負數時才能正確運作。如果權重可能是負數，則需要其他演算法（如 Bellman-Ford），但這些超出了本課程範圍。
4.3 最短路徑演算法的應用 (3.11.1)
任何需要在地圖或網絡上最小化成本、距離或時間的問題：
- 網絡路由（數據包如何在互聯網中高效傳輸）。
- 地理資訊系統 (GIS) 和導航應用（如 Google 地圖）。
- 排程和物流（找出配送的最快順序）。
Dijkstra 重點總結： Dijkstra 通過不斷更新並確認到每個節點的最短已知距離，找出加權圖（且權重非負）中的最短路徑（追蹤是關鍵技能）。
💡 進階演算法總結表 (3.11.1)
| 演算法 | 類型 | 核心數據結構 | 主要應用 |
|---|---|---|---|
| BFS | 搜尋（廣度優先） | 隊列 (FIFO) | 無權圖中的最短路徑。 |
| DFS | 搜尋（深度優先） | 堆疊 / 遞迴 (LIFO) | 迷宮導航或連通性檢查。 |
| Dijkstra's | 最短路徑 | 優先佇列（隱式，或反覆運算處理） | 加權圖（非負權重）中的最短路徑。 |