第 12 章 基礎 約 12 分鐘
圖論入門：點和線的世界
捷運路線圖、臉書好友、地圖導航——背後都是圖。先把詞彙學會，後面 BFS / DFS 才有意義。
建議先看過： 09-recursion
圖到底是什麼？
打開臉書，你和你朋友的關係看起來像這樣：
- 每個圈圈叫頂點 (Vertex / Node)——一個人。
- 每條線叫邊 (Edge)——好友關係。
- 整張圖叫 Graph。
圖的兩種類型
有向 vs 無向：
| 類型 | 例子 | 邊的意義 |
|---|---|---|
| 無向圖 (Undirected) | 臉書好友 | A 是 B 朋友 ⇔ B 是 A 朋友 |
| 有向圖 (Directed) | IG 追蹤 | A 追蹤 B ≠ B 追蹤 A |
有權重 vs 無權重：
| 類型 | 例子 |
|---|---|
| 無權重 | 「有/沒有」連線 |
| 有權重 | 兩地之間的距離、好感度、運費 |
怎麼存圖？兩種方式
電腦不能直接存「圈圈和線」，要轉成資料結構。常見兩種：
鄰接矩陣 (Adjacency Matrix)
用 n×n 的二維陣列，M[i][j] = 1 代表 i 和 j 有邊。
上面那張圖的鄰接矩陣（A=0, B=1, C=2, D=3）：
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 1 | 1 |
| C | 1 | 1 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
特性：
- 查「i 和 j 有沒有邊」O(1)——超快。
- 空間 O(n²)——n 很大（百萬點）時會爆。
- 適合稠密圖（邊很多）。
鄰接串列 (Adjacency List)
每個頂點存一個 list，裝它連到的鄰居。
A: [B, C]
B: [A, C, D]
C: [A, B, D]
D: [B, C]特性：
- 查「i 連到誰」O(鄰居數)。
- 空間 O(V + E)——點數+邊數。
- 適合稀疏圖（邊少）。實務最常用。
💡選哪個？
n < 1000 而且圖很稠密 → 鄰接矩陣簡單暴力。 n 大 / 邊稀疏 → 鄰接串列省空間。 考試題大部分用鄰接串列。
詞彙速查表
考試會出現這些字，先認識一下：
| 詞 | 意思 |
|---|---|
| Vertex / Node | 頂點 |
| Edge | 邊 |
| Adjacent | 相鄰（兩個頂點有邊連著） |
| Degree | 度數（一個頂點連幾條邊） |
| Path | 路徑（從 A 走到 B 的一連串邊） |
| Cycle | 環（走一圈回到自己） |
| Connected | 連通（任兩點都走得到） |
| Tree | 樹（無環的連通圖） |
| DAG | 有向無環圖（Directed Acyclic Graph） |
📝考試會這樣考
題型一：給圖，畫鄰接矩陣或鄰接串列。 題目給你一張圖，要你寫出兩種表示法。訣竅：列表/欄要按字母或編號順序排好，改卷比較順。
題型二：問鄰接矩陣 vs 鄰接串列的優缺點。 經典題，背起來：
| 鄰接矩陣 | 鄰接串列 | |
|---|---|---|
| 空間 | O(V²) | O(V+E) |
| 查 (i,j) 是否相鄰 | O(1) | O(degree(i)) |
| 找 i 所有鄰居 | O(V) | O(degree(i)) |
| 適合 | 稠密圖 | 稀疏圖 |
題型三：計算度數總和。 握手定理：所有頂點度數總和 = 2 × 邊數。 （每條邊貢獻 2 個度數，一邊各 1）
這章記住
- 圖 = 點 (Vertex) + 邊 (Edge)。
- 兩種存法：鄰接矩陣（小而稠密）、鄰接串列（大而稀疏，實務常用）。
- 詞彙要熟，下一章 BFS / DFS 都會用到。
學習進度只存在你的瀏覽器，不會上傳。