Graphs

✨ 進階數據結構：圖論 (Graphs) – 學習筆記

歡迎來到精彩的圖論世界！你已經掌握了陣列 (Arrays)、列表 (Lists)、堆疊 (Stacks) 和佇列 (Queues) 等線性結構，現在我們要進入處理更複雜、非線性關係的結構了。

圖 (Graphs) 是計算機科學中最強大的概念之一，對於模擬從社交網絡到導航系統等現實世界的問題至關重要。別擔心，如果剛開始覺得有些棘手，我們會將專業術語和方法逐步拆解！

1. 定義圖數據結構

圖 (Graph) 是一種用於表示物件之間複雜關係或連接的數據結構。

試著把圖想像成城市交通系統的路線圖。

1.1 核心術語

• 頂點 (Vertex / Node)： 這是圖中的獨立實體或點。
  （類比：地圖上的城市或巴士站。）
• 邊 (Edge / Arc)： 這是兩個頂點之間的連接或關係。
  （類比：連接兩座城市的道路或巴士路線。）
• 圖 (Graph)： 所有頂點和邊的集合。

1.2 圖的類型

圖有幾種不同的類型，由它們的邊的特性所定義：

a) 加權圖與非加權圖 (Weighted vs. Unweighted Graphs)

• 加權圖 (Weighted Graph)： 每條邊都有一個相關聯的數值，稱為權重 (weight)（通常稱為成本）。
  （例子：如果頂點是城市，權重可能是兩地之間的距離、旅行時間或機票成本。）
• 非加權圖 (Unweighted Graph)： 所有邊都被視為相等（或權重為 1）。目標通常只是找到最少的步驟數。

b) 有向圖與無向圖 (Directed vs. Undirected Graphs)

• 無向圖 (Undirected Graph)： 邊僅表示存在連接，但不表示移動的方向。如果頂點 A 連接到頂點 B，你可以從 A 到 B，也可以從 B 到 A。
  （例子：允許雙向通行的鄉間小路。）
• 有向圖 (Directed Graph / Digraph)： 邊帶有箭頭或方向，意味著只能單向通行。如果存在一條邊 A → B，你只能從 A 到 B，不能從 B 到 A（除非另有一條 B → A 的邊）。
  （例子：單行道或社交媒體上的追蹤關係。）

重點總結： 圖是用來模擬關係的。頂點是項目，邊是連接。權重增加了成本，而方向增加了流量控制。

2. 在記憶體中表示圖

要在電腦中儲存圖結構，我們通常使用兩種主要方法：鄰接矩陣 (Adjacency Matrix) 或 鄰接列表 (Adjacency List)。

2.1 鄰接矩陣 (Adjacency Matrix)

鄰接矩陣使用二維陣列來儲存頂點之間的連接。

• 如果圖有 \(N\) 個頂點，矩陣將會是 \(N \times N\)。
• 位置 (i, j) 的條目代表從頂點 \(i\) 到頂點 \(j\) 的邊。
• 對於非加權圖： (i, j) 通常為 1（已連接）或 0（未連接）。
• 對於加權圖： (i, j) 儲存邊的權重（成本）。如果沒有連接，我們使用 0 或一個特殊值（如無窮大）。

你知道嗎？ 在無向圖中，鄰接矩陣總是對稱的（(i, j) 的值等於 (j, i) 的值）。

2.2 鄰接列表 (Adjacency List)

鄰接列表使用陣列（或列表），其中每個索引對應一個頂點。每個索引隨後儲存一個其相鄰鄰居的列表。

例子： 如果頂點 A 連接到 B 和 C，主列表中 A 的條目將包含一個 [B, C] 的列表。對於加權圖，此列表會儲存成對的數據：[(B, 5), (C, 10)]，其中第二個數字是權重。

2.3 矩陣與列表的比較（考試關鍵！）

選擇正確的表示法很大程度上取決於圖的屬性以及執行最頻繁的操作。

鄰接矩陣的優點 (O(1) 查詢)

• 測試邊的存在性： 檢查兩個特定頂點之間是否存在邊非常快（只需檢查陣列的一個位置）。這是經常需要的操作。
• 新增/刪除邊： 簡單且快速——只需更改一個儲存格的值。
• 何時使用： 當圖是稠密圖 (dense) 時（即相對於頂點數量，邊的數量很多）。

鄰接列表的優點 (空間效率)

• 空間效率： 它只儲存實際存在的邊。如果圖是稀疏圖 (sparse)（即邊很少），列表比矩陣（無論邊有多少都總是佔用 \(N^2\) 空間）節省大量記憶體。
• 何時使用： 當圖是稀疏圖時（相對於頂點，邊的數量很少）。
• 尋找鄰居： 對於尋找特定頂點的所有鄰居非常有效。

3. 圖的遍歷演算法 (Graph Traversal Algorithms)

遍歷意味著系統地訪問圖中的每個頂點。我們需要確保不會迷路或重複訪問同一個頂點的方法。

3.1 廣度優先搜尋 (Breadth-First Search, BFS)

BFS 就像在池塘裡投入一顆鵝卵石——它會先探索當前深度（或距離）的所有頂點，然後再移動到下一層。

• 策略： 使用佇列 (Queue, FIFO) 來管理訪問頂點的順序。
• 過程：
  1. 從源頂點 (A) 開始。將 A 加入佇列並標記為已訪問。
  2. 當佇列不為空時：
  3. 從佇列中取出 (Dequeue) 當前頂點 (V)。
  4. 找出 V 的所有未訪問鄰居，將它們標記為已訪問，並將它們加入佇列 (Enqueue)。
• 典型應用： 在非加權圖中尋找最短路徑（因為它是逐層檢查的，第一次找到目的地時，保證是邊數最少的路徑）。

3.2 深度優先搜尋 (Depth-First Search, DFS)

DFS 就像在迷宮中沿著一條走廊盡可能深入，直到遇到死胡同，然後回溯以嘗試不同的路徑。

• 策略： 使用堆疊 (Stack, LIFO)，或者更常見的是使用遞迴 (recursion) 來管理過程。
• 過程：
  1. 從源頂點 (A) 開始。將 A 標記為已訪問。
  2. 探索 A 的鄰居 (B)。
  3. 對 B 遞迴地應用 DFS。
  4. 如果 B 走到死胡同，回溯到 A 並嘗試 A 的下一個未訪問鄰居。
• 典型應用： 導航迷宮或檢查連通性（圖的所有部分是否可達）。

注意陷阱： BFS 和 DFS 都需要一個機制（如布林陣列）來追蹤哪些節點已經被訪問過。這可以防止在包含循環（導向回自身的路徑）的圖中出現無限迴圈。

4. 最短路徑演算法 (Dijkstra's Algorithm)

如果圖是加權的該怎麼辦？現在，僅僅計算邊的數量是不夠的；我們需要最小化總權重（成本）。這就是 Dijkstra 演算法發揮作用的地方。

4.1 Dijkstra 最短路徑演算法

Dijkstra 演算法可以找出從一個起始頂點到加權圖中所有其他頂點的最短路徑（只要權重是非負數）。

• 目的： 找出從起始節點到每個其他節點所需的最小總權重（成本）。
• 應用： 廣泛用於網絡路由（如 GPS 和互聯網流量路由），以計算最便宜或最快的路徑。

給學生的重要提示 (教學大綱 3.11.1)：
你必須能夠使用一組數據追蹤 (trace) Dijkstra 的最短路徑演算法。
但是，除非考試題目中明確給出了演算法步驟，否則不需要背誦步驟或編寫實現該演算法的程式碼。重點應放在理解累積最小成本的*概念*上。

重點總結： BFS 在非加權圖中尋找最短路徑（最少的邊）。Dijkstra 在加權圖中尋找最短路徑（最低的總成本）。