圖的基礎#
基本概念#
| 術語 | 說明 |
|---|---|
| 頂點 (Vertex) | 圖中的節點 |
| 邊 (Edge) | 頂點之間的連接 |
| 度 (Degree) | 與頂點相連的邊數 |
| 路徑 (Path) | 頂點序列，相鄰頂點有邊相連 |
有向圖的度#
- 入分支度 (In-degree)：指向該頂點的邊數（如：粉絲數）
- 出分支度 (Out-degree)：從該頂點出發的邊數（如：關注數）
存儲方式#
1. 鄰接矩陣 (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²) |
| 方便矩陣運算 | 稀疏圖浪費空間 |
2. 鄰接串列 (Adjacency List)#
每個頂點維護一個連結串列，存儲相鄰頂點。
0: [1, 2]
1: [0, 2]
2: [0, 1, 3]
3: [2]| 優點 | 缺點 |
|---|---|
| 空間 O(V+E) | 查詢需走訪鏈結串列 |
| 適合稀疏圖 | 對快取不友好 |
選擇建議：
- 稀疏圖（邊少）→ 鄰接串列
- 稠密圖（邊多）→ 鄰接矩陣
- 需要矩陣運算 → 鄰接矩陣
鄰接串列優化#
為提升查詢效率，可將鏈結串列替換為：
- 跳表：有序，支援範圍查詢
- 紅黑樹：有序，O(log n) 查詢
- 雜湊表：O(1) 查詢，無序
社交網路存儲範例
場景：微博關注關係
- 需要查詢：A 是否關注 B？A 的粉絲有誰？
方案：
- 鄰接串列：存儲關注關係（A 關注了誰）
- 逆鄰接串列：存儲被關注關係（誰關注了 A）
- 將鏈結串列改為跳表：支援按名稱排序的分頁查詢
// 關注關係
Map<Integer, SkipList> following;
// 被關注關係（粉絲）
Map<Integer, SkipList> followers;圖的走訪複雜度#
| 演算法 | 時間複雜度 | 空間複雜度 |
|---|---|---|
| BFS | O(V + E) | O(V) |
| DFS | O(V + E) | O(V) |
V 表示頂點數，E 表示邊數。連通圖中 E >= V-1。