Graphs

歡迎來到圖論（Graphs）的世界！

在本章中，我們將探索圖（Graphs）。雖然你可能會想到數學課裡的長條圖或折線圖，但在計算機科學中，「圖」是用來表示事物之間如何連接的一種方式。

試想一下 Facebook：你是其中的一個「點」，而友誼就是連接你與他人的「線」。或者想想 Google 地圖：城市是點，道路是線。圖在我們的生活中無處不在！如果一開始覺得這概念有點抽象也別擔心，我們會把它拆解成小部分來學習。

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

圖（Graph）是一種用於表示對象對之間複雜關係的數學結構。它由兩個主要部分組成：

• 頂點（Vertex 或 Node）：圖中的「對象」或「點」（例如一個人或一個城市）。
• 邊（Edge 或 Arc）：連接頂點之間的「線」（例如一段友誼或一條道路）。

有向圖（Directed）與無向圖（Undirected）

想像節點 A 和 B 之間存在一種關係。

無向圖：邊沒有方向。如果 A 和 B 之間有一條邊，你可以雙向通行。
類比：雙向行車道或 Facebook 的好友關係（你們互為好友）。

有向圖：邊有特定的方向，通常用箭頭表示。你只能沿著箭頭的方向移動。
類比：單行道或 Twitter 的「追蹤」（你可能會追蹤某位名人，但對方不一定會追蹤你！）。

加權圖（Weighted Graphs）

有時候，節點之間的連接會有「成本」或「數值」。這被稱為加權圖。「權重（Weight）」可以代表距離、時間，甚至兩個城市之間航班的票價。

快速複習：
• 頂點（Vertex）：一個點。
• 邊（Edge）：一種連接。
• 加權（Weighted）：連接帶有數值（例如：5 英里）。
• 有向（Directed）：連接是單向的。

重點總結：圖只是節點及其之間連接的集合。它們能幫助我們建模所有事物，從網際網路到化學分子！

2. 電腦如何儲存圖

由於電腦無法直接「看見」圖的繪圖，我們需要一種方法將其轉化為數據。主要有兩種方法：

方法 A：鄰接矩陣（Adjacency Matrix）

這是一個二維陣列（格網）。行和列都代表頂點。如果兩個節點之間有連接，我們在對應位置填入 1；否則填入 0。對於加權圖，我們則在格網中儲存權重而非 1。

包含 3 個節點（A, B, C）的圖的矩陣示例：
\( \begin{matrix} & A & B & C \\ A & 0 & 1 & 0 \\ B & 1 & 0 & 1 \\ C & 0 & 1 & 0 \end{matrix} \)

方法 B：鄰接串列（Adjacency List）

這就像一本通訊錄。對於每個節點，我們保留一個清單，列出所有與它直接相連的其他節點。
示例：
A: [B]
B: [A, C]
C: [B]

哪種方法比較好？

• 鄰接矩陣：適合「稠密圖（Dense Graphs）」（幾乎所有節點都相連的情況）。它檢查「A 是否連接到 B？」非常快，但如果連接稀疏，儲存大量的 0 會浪費記憶體。
• 鄰接串列：適合「稀疏圖（Sparse Graphs）」（大部分節點沒有直接連接的情況）。它節省記憶體，因為只會儲存實際存在的連接。

你知道嗎？大多數現實世界中的圖，例如全球資訊網（World Wide Web），都是「稀疏」的。絕大多數網站只連結到所有網站中極小的一部分！

重點總結：連接多時用矩陣（速度快），連接少時用串列（節省空間）。

3. 圖的遍歷（Graph Traversal）：探索連接

遍歷的意思是「訪問圖中的每一個節點」。根據你的目標，有兩種主要方法：

深度優先搜尋（Depth-First Search, DFS）

在 DFS 中，你會盡可能沿著一條路徑走到底，然後再回溯（back-tracking）去尋找新的路徑。
記憶小撇步：把「深度（Depth）」想像成「深（Deep）」。你潛入圖的深處。
• 類比：走迷宮時，沿著一條路徑一直走，直到遇到死胡同。
• 數據結構：使用堆疊（Stack）（後進先出，LIFO）。
• 常見用途：走迷宮或檢查兩點之間是否存在路徑。

廣度優先搜尋（Breadth-First Search, BFS）

在 BFS 中，你會先訪問起始節點的所有直接相鄰節點，然後再訪問它們的所有鄰居，依此類推。
記憶小撇步：把「廣度（Breadth）」想像成「寬（Wide）」。你在圖上向四面八方擴展。
• 類比：往池塘丟一顆石頭，看著漣漪一圈一圈向外擴散。
• 數據結構：使用佇列（Queue）（先進先出，FIFO）。
• 常見用途：在無權重圖中尋找最短路徑（例如：你在 LinkedIn 上與陌生人之間最少經過幾個「跳躍」）。

快速複習：
• DFS：使用堆疊，深入探索，適合走迷宮。
• BFS：使用佇列，廣泛擴散，尋找最短路徑（無權重圖）。

4. Dijkstra 最短路徑演算法

雖然 BFS 以「跳躍次數」來尋找最短路徑，但 Dijkstra 演算法是在邊有權重（例如英里或分鐘）時，尋找最短路徑的方法。

運作原理（核心概念）：

1. 從起始節點開始，將其距離設為 0，將其他所有節點的距離設為「無限大」。
2. 查看當前節點的所有未訪問鄰居。
3. 計算到每個鄰居的距離：（當前節點的距離 + 邊的權重）。
4. 如果這個新距離比該鄰居目前儲存的距離更小，就更新它！
5. 將當前節點標記為「已訪問」。你之後再也不會訪問它了。
6. 移動到距離最小的未訪問節點，重複上述步驟，直到所有節點都被訪問。

常見錯誤：學生常會忘記在發現更短的路徑時更新距離。務必檢查新計算的路徑是否比舊的「更便宜」！

現實世界應用：這正是你的衛星導航或 Google 地圖計算回家最快路線的方法。它將每個路口視為節點，將每條道路視為加權邊。

重點總結：Dijkstra 是在加權圖中尋找最短路線的「黃金標準」。它是一個最佳化（Optimisation）演算法。

5. 總結檢查清單

在完成本章之前，確保你可以：
• 定義頂點（Vertex）和邊（Edge）。
• 解釋有向圖與無向圖的區別。
• 為簡單的圖繪製鄰接矩陣和鄰接串列。
• 描述 DFS 和 BFS 如何探索圖，以及它們分別使用什麼數據結構。
• 解釋 Dijkstra 演算法的目的，並將其識別為加權圖中的最短路徑工具。

繼續練習手繪這些圖表——一旦你能畫出矩陣和串列，演算法的邏輯就會變得非常容易視覺化！