Tree 是特殊的 Graph，Graph 才是描述「關係」的終極資料結構。
一切關係都能畫成圖
Graph 由節點和邊組成，能表達任何「東西之間有關係」的場景。兩種存法：鄰接矩陣（查邊快、吃空間）和鄰接表（省空間、查邊慢）。兩種走法：BFS（一層一層擴散，找最短路）和 DFS（一條路走到底，找所有路）。
節點 + 邊 = 圖
1 --- 2
| |
3 --- 4節點（Vertex）：1, 2, 3, 4 邊（Edge）：(1,2), (1,3), (2,4), (3,4)
社交網路的好友關係、網頁之間的超連結、城市之間的道路——都是 Graph。Tree 其實是「無環連通圖」的特例。
四種圖，四種脾氣
「圖」不是只有一種長相。邊有沒有方向、帶不帶權重、准不准有環，這三個開關決定了你手上這張圖能套哪些演算法。
| 類型 | 差別 | 典型場景 |
|---|---|---|
| 無向圖 | A–B 等於 B–A | 好友關係（互相加才算） |
| 有向圖 | A→B 不等於 B→A | Twitter 追蹤、網頁超連結 |
| 有權圖 | 邊上帶數字（距離、成本） | 地圖找最短路、網路延遲 |
| 無環圖（DAG） | 保證沒有環 | 任務排程、build 依賴、Git 的 commit 圖 |
這不是分類癖，是會害你選錯工具的分岔。同樣一句「找最短路」，在無權圖上是 BFS 的活，在有權圖上就得換 Dijkstra——BFS 只會數「經過幾條邊」，它根本不看邊上的權重，拿去跑有權圖會理直氣壯地給你錯答案。
兩種存法
鄰接矩陣：開一個 V×V 的二維陣列，matrix[i][j] = 1 表示有邊。
1 2 3 4
1 [ 0, 1, 1, 0 ]
2 [ 1, 0, 0, 1 ]
3 [ 1, 0, 0, 1 ]
4 [ 0, 1, 1, 0 ]查「i 和 j 之間有沒有邊」是 O(1)，但空間是 O(V²)。社交網路有十億用戶，你不會想開一個十億乘十億的矩陣。
鄰接表：每個節點存一份鄰居列表。
1 → [2, 3]
2 → [1, 4]
3 → [1, 4]
4 → [2, 3]空間 O(V + E)，查邊要遍歷鄰居列表。但實際上大部分圖都是稀疏的（邊遠少於 V²），所以鄰接表是最常用的。
BFS：水波擴散
BFS 用 Queue，像丟石頭到水裡的漣漪，一圈一圈往外擴。
從 1 開始：
第 1 層: [1]
第 2 層: [2, 3] ← 1 的鄰居
第 3 層: [4] ← 2 和 3 的鄰居（扣掉已訪問的）Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
int v = queue.poll();
for (int neighbor : graph.get(v)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}BFS 的關鍵特性：第一次到達某節點的路徑一定是最短路徑（無權圖）。這就是為什麼找最短路要用 BFS 不是 DFS。
DFS：一條路走到黑
DFS 用 Stack（或遞迴），先一直往深處走，走到底了再回頭。
void dfs(int v) {
visited.add(v);
for (int neighbor : graph.get(v)) {
if (!visited.contains(neighbor))
dfs(neighbor);
}
}DFS 適合：拓撲排序、環檢測、找連通分量、回溯法（backtracking）。
BFS vs DFS 選擇
問自己一個問題：「我要找最短的那一條，還是要找所有可能的路？」
找最短 → BFS。探索全部 → DFS。
兩者時間複雜度都是 O(V + E)。
經典圖論問題
| 問題 | 演算法 |
|---|---|
| 最短路徑（無權） | BFS |
| 最短路徑（有權） | Dijkstra |
| 最小生成樹 | Prim / Kruskal |
| 拓撲排序 | DFS |
| 環檢測 | DFS |
| 連通分量 | BFS/DFS 或 Union-Find |
🎬 互動視覺化： DFS 遍歷動畫 — 自己擺節點、連邊，看 Queue 和 Stack 怎麼一步步吐出遍歷順序，「水波擴散」和「一條路走到黑」的差別一眼就看穿。
Graph 是資料結構的終極形態——當你的資料不是線性的、不是階層的，而是「任何東西都可能跟任何東西有關」的時候，你需要的就是它。
接下來往哪走
- Advanced Graph 進階圖論 — Dijkstra、拓撲排序、最小生成樹怎麼實作
- Union-Find 併查集 — 連通分量與環檢測的高效解
- Heap 堆積 — Dijkstra 的 priority queue 底層就是它