基礎圖論講了最短路徑和拓撲排序。這篇進入深水區：MST、SCC、割點、二分圖。這些不是面試常客（除了 MST），但在系統設計和競賽裡會遇到。
先講結論
| 演算法 | 解決什麼 | 複雜度 |
|---|---|---|
| Prim / Kruskal | 最小生成樹 | O(E log V) / O(E log E) |
| Tarjan / Kosaraju | 強連通分量 | O(V + E) |
| 割點橋演算法 | 找關鍵節點/邊 | O(V + E) |
| BFS 染色 | 二分圖判定 | O(V + E) |
| 匈牙利演算法 | 二分圖最大匹配 | O(VE) |
最小生成樹 MST
用最少的邊權重連接所有節點。想像你要鋪光纖連接所有城市——花最少的錢把大家都連上。
Kruskal：按邊權重排序，依序加入不形成環的邊。用 Union-Find 判斷是否成環。適合稀疏圖。
Prim：從一個點開始，每次加入「離已連接部分最近」的新點。用 Priority Queue 找最近的。適合稠密圖。
// Prim 的核心邏輯
PriorityQueue<int[]> pq; // (權重, 節點)
pq.add({0, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
if (已在 MST) continue;
加入 MST;
for (鄰居 v : neighbors(curr))
if (!在 MST) pq.add({weight, v});
}怎麼選？邊少用 Kruskal，邊多用 Prim。面試通常考 Kruskal，因為 Union-Find 是另一個考點。
強連通分量 SCC
有向圖中，任意兩點可以互達的最大子圖。
┌─→ 1 ─→ 2 ─┐
│ ↖ ↓ │
0 ↖─────┘
└─→ 3 ─→ 4
SCC: {0,1,2}, {3}, {4}
0、1、2 之間可以互相到達，所以是一個 SCC。3 和 4 各自獨立。
Tarjan 演算法
一次 DFS 搞定。核心概念：
dfn[u]：u 被發現的時間low[u]：u 能回溯到的最早祖先的發現時間- 如果
low[u] == dfn[u]，u 就是一個 SCC 的根
dfn[u] = low[u] = time++;
stack.push(u);
for (v in neighbors) {
if (!visited[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if (onStack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
// 彈出 stack 直到 u → 一個 SCC
}Tarjan 的精妙之處在於它用 stack 和 low 值，在一次 DFS 中同時完成發現和分類。但說實話，我每次重新理解 Tarjan 都要花半小時。
割點與橋
割點：移除後圖不連通的節點。橋：移除後圖不連通的邊。
在網路拓撲裡，割點就是「單點故障」——那台 router 掛了整個網路就斷了。找出割點，就知道哪裡需要冗餘備份。
判定條件（也是用 Tarjan 的 DFS tree）：
- 割點：子節點無法不經過 u 回到 u 的祖先（
low[v] >= dfn[u]） - 橋：v 完全無法回到 u 或更早（
low[v] > dfn[u]）
二分圖
節點可以分成兩組，邊只存在於組間。判定方法：BFS/DFS 染色，相鄰節點不同色。如果染色過程遇到衝突，就不是二分圖。
A 組 B 組
0 ─────── 1
│ │
2 ─────── 3
匈牙利演算法：最大匹配
在二分圖中找最多的配對。核心邏輯：
boolean dfs(int u) {
for (int v : neighbors[u]) {
if (!used[v]) {
used[v] = true;
if (match[v] == -1 || dfs(match[v])) {
match[v] = u;
return true;
}
}
}
return false;
}「如果你的對象已經配對了，試著讓他的對象去找別人。」這大概是演算法裡最像社交的邏輯了。
應用場景：工作分配（人 ↔ 任務）、資源排程、甚至是穩定婚姻問題。
網路流
解決最大流問題。Ford-Fulkerson、Edmonds-Karp、Dinic 是常見的演算法。這個主題太深了，除非你在打競賽或做物流系統，否則不太會遇到。知道它存在就好。
進階圖論就像高數裡的多元微積分——學的時候覺得「這什麼鬼」，但真的用到的時候會慶幸自己學過。只是那個「用到」的機會可能比你想像的少。