圖論算法導論
歡迎！今天我們將深入探討計算機科學中最強大的工具之一：圖（Graphs）。別被它的名字誤導了——這可不是數學課裡看到的長條圖或折線圖。在計算機科學中，圖是一種用來描繪事物之間關係的映射方式。
想想 Instagram 這類社交網絡，或是 Google Maps 這類地圖應用程式。這些 App 是如何知道誰是你的「建議好友」，或是如何找到前往咖啡店的最快路徑？答案就在於圖算法（Graph Algorithms）。在本章中，我們將學習如何表示這些連接，以及如何有效地「遍歷」這些路徑。
1. 什麼是圖？
簡單來說，圖就是由「點」與連接這些點的「線」所組成的集合。
關鍵術語：
- 頂點（Vertex 或 Node）： 單一個點或物件（例如一個城市或一個人）。複數為 Vertices。
- 邊（Edge）： 連接兩個頂點之間的連結（例如城市之間的道路或人與人之間的友誼）。
圖的類型
並非所有的連結都是一樣的！我們根據邊的運作方式對圖進行分類：
- 無向圖（Undirected Graph）： 連接是雙向的。如果甲是乙的朋友，那麼乙也是甲的朋友。可以想像成一條雙向道。
- 有向圖（Directed Graph / Digraph）： 連接有特定的方向。例如在 X（前身為 Twitter）上，你可能會追蹤某位明星，但他們不一定會追蹤你。這就像是一條單行道。
- 加權圖（Weighted Graph）： 邊上帶有「成本」或「數值」。例如，連接兩個城市的邊可能有一個權重 50，代表 50 公里。
- 無權圖（Unweighted Graph）： 所有邊都是相等的。我們只關心連接是否存在，而不考慮距離或成本。
快速回顧： 將圖想像成一張地圖。城市就是頂點，連接它們的道路就是邊。如果道路是單行道，它就是有向圖；如果道路標示了距離，它就是加權圖。
2. 在代碼中表示圖
計算機無法「看見」圖的繪圖，所以我們必須以計算機理解的方式來存儲數據。主要有兩種方法：
A. 鄰接矩陣（Adjacency Matrix）
這是一個二維陣列（網格），行與列代表頂點。如果頂點 A 與頂點 B 之間有連接，我們就在對應的網格中填入 1，否則填入 0。
矩陣範例：
如果我們有 3 個節點（0, 1, 2），且 0 與 1 之間有連接：
\( \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \)
- 優點： 檢查兩個特定節點是否連接時速度非常快。
- 缺點： 如果節點多但連接少（全是零），會浪費大量記憶體。
B. 鄰接列表（Adjacency List）
這就像一本「通訊錄」。每個頂點都保存著一個列表，記錄了所有與它直接相連的其他頂點。
列表範例：
節點 0: [1, 2]
節點 1: [0]
節點 2: [0]
- 優點： 節省空間！我們只儲存實際存在的連接。
- 缺點： 檢查特定連接是否存在較慢，因為你必須在列表中進行搜尋。
記憶小撇步： 當圖是「稠密」的（連接很多）時，使用矩陣；當圖是「稀疏」的（大部分空間是空的）時，使用列表。
3. 圖遍歷：探索連接
遍歷是一個專業術語，意指「訪問圖中的每一個節點」。主要有兩種方法，它們的操作方式就像探索一棟建築或一個迷宮一樣。
A. 廣度優先搜尋（Breadth-First Search, BFS）
想像你把一顆小石子丟進池塘裡。漣漪會一圈圈地向外擴散，先觸及最近的點，然後是下一個圈，依此類推。這就是 BFS！
運作原理：
- 從一個節點開始，並將其標記為「已訪問」。
- 首先訪問它所有的直接相鄰節點。
- 然後訪問這些鄰居的鄰居。
- 使用佇列（Queue，先進先出）來追蹤下一個要訪問的節點。
適用情境： 在無權圖中尋找最短路徑。
B. 深度優先搜尋（Depth-First Search, DFS）
想像你在探索一個迷宮。你選定一條路並盡可能地深入，直到碰到死胡同為止。然後你回頭並嘗試下一個可用的轉彎。這就是 DFS！
運作原理：
- 從一個節點開始，並將其標記為「已訪問」。
- 順著一條路徑盡可能地走到底。
- 當碰到死胡同（或已訪問過的節點）時，回溯到上一個還有未訪問鄰居的節點。
- 使用堆疊（Stack，後進先出）或遞迴（Recursion）來追蹤路徑。
適用情境： 檢查兩個節點之間是否存在路徑，或是解決需要嘗試所有可能性的謎題。
別擔心，如果覺得很複雜！ 只要記住：BFS 用於 Breadth（廣度，向外擴散），而 DFS 用於 Depth（深度，往深處走）。
4. 要避免的常見陷阱
- 無限迴圈： 如果你不追蹤「已訪問」的節點，你的算法可能會永遠繞圈子。務必將訪問過的節點標記下來！
- 錯誤的數據結構： 記得 BFS 使用佇列，而 DFS 使用堆疊。搞混它們會改變算法探索圖的方式。
- 有向圖 vs 無向圖： 在有向圖中，能從 A 到 B 不代表能從 B 到 A。一定要看清楚箭頭方向！
重點總結
頂點是點，邊是線。圖可以是有向的（單向）或無向的（雙向），也可以是加權的（帶有成本）或無權的（無成本）。要存儲它們，請使用鄰接矩陣（適用於大量連接）或鄰接列表（節省空間）。要搜尋它們，請使用 BFS（廣度/佇列）來找最短路徑，或使用 DFS（深度/堆疊）來探索所有路徑。
你知道嗎？ 「六度分隔理論」（世界上任何人之間透過六個或更少的中間人就能建立聯繫）其實就是一個可以用廣度優先搜尋來解決的圖論問題！