圖的基礎 (Graph Basics)#
基本概念#
| 術語 | 說明 |
|---|---|
| 頂點 (Vertex) | 圖中的節點 |
| 邊 (Edge) | 頂點之間的連接 |
| 度 (Degree) | 與頂點相連的邊數 |
| 路徑 (Path) | 頂點序列，相鄰頂點有邊相連 |
有向圖的度#
- 入度 (In-degree)：指向該頂點的邊數（如：粉絲數）
- 出度 (Out-degree)：從該頂點出發的邊數（如：追蹤數）
存儲方式#
鄰接矩陣 (Adjacency Matrix)#
使用二維陣列 A[i][j] 表示頂點 i 到 j 是否有邊。
0 1 2 3
0 [ 0, 1, 1, 0 ]
1 [ 1, 0, 1, 0 ]
2 [ 1, 1, 0, 1 ]
3 [ 0, 0, 1, 0 ]| 優點 | 缺點 |
|---|---|
查詢 O(1) | 空間 O(V²) |
| 方便矩陣運算 | 稀疏圖浪費空間 |
鄰接串列 (Adjacency List)#
每個頂點維護一個連結串列，存儲相鄰頂點。
0: [1, 2]
1: [0, 2]
2: [0, 1, 3]
3: [2]在 Kotlin 中，最常見的表示法是用 MutableList 陣列：
// graph[i] 存頂點 i 的所有鄰居
val graph = Array(n) { mutableListOf<Int>() }
fun addEdge(u: Int, v: Int) {
graph[u].add(v)
graph[v].add(u) // 無向圖雙向加；有向圖只保留單向的其中一行
}| 優點 | 缺點 |
|---|---|
空間 O(V+E) | 查詢需走訪鏈結串列 |
| 適合稀疏圖 | 對快取不友好 |
選擇建議：
- 稀疏圖（邊少）➡️ 鄰接串列
- 稠密圖（邊多）➡️ 鄰接矩陣
- 需要矩陣運算 ➡️ 鄰接矩陣
鄰接串列最佳化#
為提升查詢效率，可將鏈結串列替換為：
- 跳表：有序，支援範圍查詢
- 紅黑樹：有序，
O(log n)查詢 - 雜湊表：
O(1)查詢，無序
社交網路存儲範例
場景：X (Twitter) 追蹤關係
- 需要查詢：A 是否追蹤 B？A 的粉絲有誰？
方案：
- 鄰接串列：存儲追蹤關係（A 追蹤了誰）
- 逆鄰接串列：存儲被追蹤關係（誰追蹤了 A）
- 將鏈結串列改為跳表：支援按名稱排序的分頁查詢
// 追蹤關係
val following: HashMap<Int, SkipList>
// 被追蹤關係（粉絲）
val followers: HashMap<Int, SkipList>圖的走訪複雜度#
| 演算法 | 時間複雜度 | 空間複雜度 |
|---|---|---|
| BFS | O(V + E) | O(V) |
| DFS | O(V + E) | O(V) |
V 表示頂點數，E 表示邊數。連通圖中 E >= V-1。