02.12.1 强连通分量与 Tarjan 及割点桥
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.12 图与字符串进阶
覆盖范围
- Tarjan 求 SCC
- Kosaraju 算法
- 割点与桥
- 缩点 DAG
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 02.12.1-001 | Tarjan 求强连通分量 | 高级 | ★★★★ |
| 02.12.1-002 | Kosaraju 算法 | 进阶 | ★★★ |
| 02.12.1-003 | 割点判定 | 进阶 | ★★★ |
| 02.12.1-004 | 桥判定 | 进阶 | ★★★ |
| 02.12.1-005 | 缩点 DAG | 高级 | ★★★ |
| 02.12.1-006 | Tarjan 伪代码 | 高级 | ★★★★ |
| 02.12.1-007 | 强连通分量应用 | 进阶 | ★★★ |
| 02.12.1-008 | 点双与边双连通分量 | 高级 | ★★ |
02.12.1-001 Tarjan 求强连通分量
频率 ★★★★ | 难度 高级
一句话结论
Tarjan 用 DFS,维护 dfn[u](访问时间)和 low[u](子树中能回到的最早 dfn);栈存当前路径上的节点;当 low[u] == dfn[u] 时,栈中 u 及以上节点构成一个 SCC。
概念解释
- dfn[u]:DFS 访问 u 的时间戳。
- low[u]:u 或 u 的子树中能通过一条回边回到的最早 dfn。
- 栈:存当前 DFS 路径上的节点。
- SCC 判定:low[u] == dfn[u] 时,栈中 u 及以上构成 SCC。
原理流程
- dfn[u] = low[u] = ++time,u 入栈。
- 遍历 u 的邻接 v:
- 若 v 未访问:dfs(v),low[u] = min(low[u], low[v])。
- 若 v 在栈中:low[u] = min(low[u], dfn[v])。
- 若 low[u] == dfn[u]:弹出栈直到 u,这些节点构成 SCC。
代码 / 示例
class TarjanSCC {
private int time = 0;
private final int[] dfn, low;
private final boolean[] inStack;
private final java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
private final java.util.List<java.util.List<Integer>> sccs = new java.util.ArrayList<>();
private final java.util.List<Integer>[] graph;
TarjanSCC(java.util.List<Integer>[] graph) {
this.graph = graph;
int n = graph.length;
dfn = new int[n]; low = new int[n]; inStack = new boolean[n];
}
void dfs(int u) {
dfn[u] = low[u] = ++time;
stack.push(u); inStack[u] = true;
for (int v : graph[u]) {
if (dfn[v] == 0) {
dfs(v);
low[u] = Math.min(low[u], low[v]);
} else if (inStack[v]) {
low[u] = Math.min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
java.util.List<Integer> scc = new java.util.ArrayList<>();
while (true) {
int x = stack.pop();
inStack[x] = false;
scc.add(x);
if (x == u) break;
}
sccs.add(scc);
}
}
}
常见误区
- 误区:回边用 low[v] 而不是 dfn[v];正解:回边(v 在栈中)用 dfn[v],因为 low[v] 可能包含已经弹出的 SCC。
- 误区:low[u] == dfn[u] 才弹栈;正解:是的,这是 SCC 根节点。
追问 / 延伸
- Q:时间复杂度? A:O(V+E)。
- Q:Tarjan vs Kosaraju? A:Tarjan 一次 DFS,Kosaraju 两次 DFS,Tarjan 更省。
02.12.1-002 Kosaraju 算法
频率 ★★★ | 难度 进阶
一句话结论
Kosaraju 两次 DFS:第一次在原图 DFS 按完成时间压栈;第二次在逆图按栈顺序 DFS,每次 DFS 树就是一个 SCC。
概念解释
- 第一次 DFS:原图,按完成时间压栈。
- 逆图:所有边反向。
- 第二次 DFS:逆图,按栈顶顺序 DFS,每次 DFS 树 = 一个 SCC。
原理流程
- 第一次 DFS 原图,记录完成顺序(栈)。
- 建逆图。
- 按栈顶顺序在逆图 DFS,每次 DFS 树就是一个 SCC。
代码 / 示例
class Kosaraju {
private final java.util.List<Integer>[] graph, revGraph;
private final boolean[] visited;
private final java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
private final java.util.List<java.util.List<Integer>> sccs = new java.util.ArrayList<>();
Kosaraju(java.util.List<Integer>[] graph) {
this.graph = graph;
int n = graph.length;
revGraph = new java.util.List[n];
for (int i = 0; i < n; i++) {
revGraph[i] = new java.util.ArrayList<>();
for (int v : graph[i]) revGraph[v].add(i);
}
visited = new boolean[n];
}
void dfs1(int u) {
visited[u] = true;
for (int v : graph[u]) if (!visited[v]) dfs1(v);
stack.push(u);
}
void dfs2(int u, java.util.List<Integer> scc) {
visited[u] = true;
scc.add(u);
for (int v : revGraph[u]) if (!visited[v]) dfs2(v, scc);
}
void compute() {
for (int i = 0; i < graph.length; i++) if (!visited[i]) dfs1(i);
java.util.Arrays.fill(visited, false);
while (!stack.isEmpty()) {
int u = stack.pop();
if (!visited[u]) {
java.util.List<Integer> scc = new java.util.ArrayList<>();
dfs2(u, scc);
sccs.add(scc);
}
}
}
}
常见误区
- 误区:第二次 DFS 在原图;正解:第二次在逆图。
- 误区:按栈底顺序;正解:按栈顶顺序(完成时间最晚的先)。
追问 / 延伸
- Q:时间复杂度? A:O(V+E),两次 DFS。
- Q:Kosaraju 优点? A:思路直观,逆图 + 两次 DFS。
02.12.1-003 割点判定
频率 ★★★ | 难度 进阶
一句话结论
割点是删除后图不连通的节点;Tarjan 判定:根节点有 >= 2 个子树则是割点;非根节点 u 存在子节点 v 满足 low[v] >= dfn[u],则 u 是割点(v 的子树无法绕回 u 的祖先)。
概念解释
- 割点:删除后图不连通。
- 根节点:子树数 >= 2 则是割点。
- 非根节点:存在子节点 v,low[v] >= dfn[u],则 u 是割点。
原理流程
- DFS 维护 dfn 和 low。
- 根节点:子树数 >= 2 则割点。
- 非根节点:存在子节点 v,low[v] >= dfn[u],则 u 是割点。
代码 / 示例
// 割点判定(在 Tarjan DFS 中)
int children = 0;
for (int v : graph[u]) {
if (dfn[v] == 0) {
children++;
dfs(v);
low[u] = Math.min(low[u], low[v]);
if (parent != -1 && low[v] >= dfn[u]) isArticulation[u] = true;
} else {
low[u] = Math.min(low[u], dfn[v]);
}
}
if (parent == -1 && children >= 2) isArticulation[u] = true;
常见误区
- 误区:根节点也用 low[v] >= dfn[u];正解:根节点用子树数 >= 2。
- 误区:low[v] > dfn[u] 而不是 >=;正解:>= 即可,等于说明 v 的子树只能回到 u。
追问 / 延伸
- Q:割点和桥的关系? A:割点是节点,桥是边,判定类似但条件不同。
- Q:时间复杂度? A:O(V+E)。
02.12.1-004 桥判定
频率 ★★★ | 难度 进阶
一句话结论
桥是删除后图不连通的边;Tarjan 判定:边 (u, v) 是桥当且仅当 low[v] > dfn[u](v 的子树无法绕回 u 或 u 的祖先)。
概念解释
- 桥:删除后图不连通的边。
- 判定:low[v] > dfn[u]。
- 区别割点:割点是 >=,桥是 >。
原理流程
- DFS 维护 dfn 和 low。
- 对树边 (u, v)(v 是 u 的子节点):
- 若 low[v] > dfn[u],则 (u, v) 是桥。
代码 / 示例
// 桥判定(在 Tarjan DFS 中)
for (int v : graph[u]) {
if (dfn[v] == 0) {
dfs(v);
low[u] = Math.min(low[u], low[v]);
if (low[v] > dfn[u]) bridge(u, v);
} else if (v != parent) {
low[u] = Math.min(low[u], dfn[v]);
}
}
常见误区
- 误区:桥判定用 >=;正解:桥用 >,割点用 >=。
- 误区:忽略 parent 边;正解:无向图 DFS 中要跳过 parent 边。
追问 / 延伸
- Q:桥和割点区别? A:桥是边,割点是节点;桥条件 >,割点条件 >=。
- Q:时间复杂度? A:O(V+E)。
02.12.1-005 缩点 DAG
频率 ★★★ | 难度 高级
一句话结论
把每个 SCC 缩成一个点,SCC 之间的边构成 DAG(无环);缩点后可以做拓扑排序、DP 等;DAG 上的问题比一般图简单。
概念解释
- 缩点:每个 SCC 变成一个点。
- DAG:SCC 之间无环。
- 应用:拓扑排序、DP、最长路。
原理流程
- Tarjan 求所有 SCC。
- 每个 SCC 编号为一个节点。
- SCC 之间的边构成 DAG。
- 在 DAG 上做拓扑排序或 DP。
代码 / 图示
原图:有环
缩点:每个 SCC 一个点
结果:DAG(无环)
常见误区
- 误区:缩点后还有环;正解:SCC 之间无环,因为如果有环则两个 SCC 应合并。
- 误区:缩点后边重复;正解:需要去重,避免重复边。
追问 / 延伸
- Q:缩点后做什么? A:拓扑排序、DP、最长路。
- Q:时间复杂度? A:O(V+E)。
02.12.1-006 Tarjan 伪代码
频率 ★★★★ | 难度 高级
一句话结论
Tarjan DFS:设 dfn[u] = low[u] = ++time,u 入栈;遍历邻接 v:未访问则递归并更新 low[u] = min(low[u], low[v]),已访问且在栈中则 low[u] = min(low[u], dfn[v]);low[u] == dfn[u] 时弹栈成 SCC。
概念解释
- dfn:访问时间。
- low:子树能回到的最早 dfn。
- 栈:当前路径上的节点。
- 弹栈:low[u] == dfn[u] 时。
原理流程
见代码。
代码 / 示例
tarjan(u):
dfn[u] = low[u] = ++time
stack.push(u); inStack[u] = true
for v in adj[u]:
if dfn[v] == 0:
tarjan(v)
low[u] = min(low[u], low[v])
else if inStack[v]:
low[u] = min(low[u], dfn[v])
if low[u] == dfn[u]:
repeat:
x = stack.pop()
inStack[x] = false
scc.add(x)
until x == u
常见误区
- 误区:回边用 low[v];正解:回边用 dfn[v]。
- 误区:弹栈条件 low[u] < dfn[u];正解:== 才弹栈。
追问 / 延伸
- Q:Tarjan 时间复杂度? A:O(V+E)。
- Q:Tarjan 能求桥和割点吗? A:能,判定条件不同。
02.12.1-007 强连通分量应用
频率 ★★★ | 难度 进阶
一句话结论
SCC 用于:缩点后做 DAG 上的 DP(如最长路)、2-SAT(强连通分量判断可满足性)、社交网络分析(社区发现)。
概念解释
- 2-SAT:每个变量取正反两个点,条件转化为边,SCC 判断可满足性。
- 缩点 DP:DAG 上做最长路/最短路。
- 社区发现:SCC 内节点互相可达。
原理流程
- 2-SAT:变量 x 拆成 x=true 和 x=false,条件转化为蕴含边;若 x 和 !x 在同一 SCC 则不可满足。
- 缩点 DP:SCC 缩成点,DAG 上拓扑排序 DP。
代码 / 图示
2-SAT:
x = true 或 x = false
条件 (a or b) -> 边 !a -> b, !b -> a
若 x 和 !x 在同一 SCC -> 不可满足
常见误区
- 误区:2-SAT 用 Tarjan 还是 Kosaraju? A:都可以,Tarjan 更省。
- 误区:SCC 内节点等价;正解:SCC 内节点互相可达,在 2-SAT 中可同时取。
追问 / 延伸
- Q:2-SAT 是什么? A:每个变量取 true/false,条件是两个变量的或,求是否可满足。
- Q:SCC 还能做什么? A:缩点后做拓扑排序、DP、最短路径。
02.12.1-008 点双与边双连通分量
频率 ★★ | 难度 高级
一句话结论
边双连通分量:内部没有桥(删除任意一条边仍连通);点双连通分量:内部没有割点(删除任意一个节点仍连通);两者都用 Tarjan 判定。
概念解释
- 边双连通:无桥,删除任意边仍连通。
- 点双连通:无割点,删除任意节点仍连通。
- 判定:桥的两个端点属于不同边双;割点可能属于多个点双。
原理流程
- 边双连通:先求所有桥,桥把图分成边双。
- 点双连通:Tarjan 求割点,割点把图分成点双。
代码 / 图示
边双连通:无桥
点双连通:无割点
常见误区
- 误区:边双和点双相同;正解:边双是无桥,点双是无割点。
- 误区:割点属于一个点双;正解:割点可能属于多个点双。
追问 / 延伸
- Q:边双和点双区别? A:边双删边仍连通,点双删节点仍连通。
- Q:时间复杂度? A:O(V+E)。
待整理清单
- [ ] 2-SAT 详细
- [ ] 圆方树
- [ ] 强连通分量在工程中的应用