02.4.2.2 拓扑排序与环检测
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.2 图论与并查集
02.4.2.2-001 什么是拓扑排序?
一句话结论
对有向无环图(DAG)排出顶点线性序,使每条有向边 u→v 中 u 排在 v 前;用于依赖任务排序;存在环则无拓扑序。
概念解释
- DAG:有向无环。
- 依赖前置:边指向后继。
- 线性序满足先后。
原理流程
- 确认无环。
- 入度清零者先排。
- 移除该顶点更新入度。
代码 / 图示
A → B → C
拓扑序:A, B, C
常见误区
- 误区:任何图都能拓扑排序;正解:有环无解。
- 误区:拓扑序唯一;正解:通常有多解。
追问
- Q:拓扑序用途? A:编译依赖、课程先修、任务调度。
- Q:环存在时输出什么? A:无解/空序列。
02.4.2.2-002 Kahn 算法怎么做?
一句话结论
统计各顶点入度,入度为 0 入队;弹出一个加入结果,其邻接点入度减一,减到 0 入队;结果数等于 V 即无环;O(V+E) 时间 O(V) 队列。
概念解释
- 入度:前置依赖数。
- 零入度可先做。
- 移除解锁后继。
原理流程
- 建图统计入度。
- 零入度入队。
- 循环弹出并降级邻接。
代码 / 示例
public List<Integer> topoSort(int n, List<Integer>[] g, int[] indeg) {
List<Integer> res = new ArrayList<>();
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
while (!q.isEmpty()) {
int u = q.poll();
res.add(u);
for (int v : g[u]) if (--indeg[v] == 0) q.offer(v);
}
return res.size() == n ? res : new ArrayList<>();
}
常见误区
- 误区:边方向搞反导致入度错;正解:
u→v,v 入度加一。 - 误区:结果数不足 V 未判环;正解:结果 < V 即有环。
追问
- Q:Kahn 结果不唯一? A:零入度多者队列顺序可变。
- Q:队列改栈? A:仍可得拓扑序,顺序不同。
02.4.2.2-003 DFS 后序怎么做拓扑排序?
一句话结论
DFS 访问节点,递归完所有邻接点后把节点加入结果;逆后序即拓扑序;三色标记同时检测环;O(V+E) 时间 O(V) 递归栈。
概念解释
- 后序:子节点先完成。
- 逆序:父在前。
- 环检测三色。
原理流程
- 枚举未访问节点 DFS。
- 邻接递归完再加入列表。
- 列表反转得拓扑序。
代码 / 示例
void dfs(int u) {
state[u] = 1;
for (int v : g[u]) {
if (state[v] == 1) throw new RuntimeException("cycle");
if (state[v] == 0) dfs(v);
}
state[u] = 2;
order.add(u);
}
// 反转 order 得拓扑序
常见误区
- 误区:前序加入即拓扑序;正解:后序完成后再加入,结果需反转。
- 误区:遇访问中节点未判环;正解:灰节点即环。
追问
- Q:逆后序为什么满足依赖? A:后继先完成入列,反转后前置在前。
- Q:递归爆栈? A:改迭代后序或 Kahn。
02.4.2.2-004 拓扑排序怎么判断有环?
一句话结论
Kahn 处理后结果数 < V 说明残留节点入度无法清零,存在环;DFS 三色遇访问中节点判环;两种方法等价。
概念解释
- 环上节点入度永不为 0。
- 三色在栈判定。
- 两种判环口径。
原理流程
- Kahn 统计处理数。
- 不足 V 即环。
- 或 DFS 遇灰返回环。
代码 / 图示
Kahn:processed < n → 环
DFS:遇 state=1 → 环
常见误区
- 误区:环上节点也能被 Kahn 弹出;正解:环内入度互不为零。
- 误区:无向图直接套有向拓扑;正解:无向环用父节点排除。
追问
- Q:环检测出环上节点? A:记录 DFS 栈路径。
- Q:自环算环吗? A:算,入度无法清零。
02.4.2.2-005 课程表 I(LC 207)能否修完所有课?
一句话结论
先修关系建成有向图 先修→后修,Kahn 或 DFS 判环;无环可修完,有环返回 false;O(V+E) 时间。
概念解释
- 边:先修指向后续。
- 环:循环依赖。
- 可完成 = 无环。
原理流程
- 建图统计入度。
- Kahn 处理全部课程。
- 处理数等于课程数返回 true。
代码 / 示例
public boolean canFinish(int numCourses, int[][] prereq) {
List<Integer>[] g = new List[numCourses];
int[] indeg = new int[numCourses];
for (int i = 0; i < numCourses; i++) g[i] = new ArrayList<>();
for (int[] p : prereq) {
g[p[1]].add(p[0]);
indeg[p[0]]++;
}
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
int done = 0;
while (!q.isEmpty()) {
int u = q.poll(); done++;
for (int v : g[u]) if (--indeg[v] == 0) q.offer(v);
}
return done == numCourses;
}
常见误区
- 误区:边方向写反;正解:先修 → 后修。
- 误区:只判队列空不统计完成数;正解:需对比课程总数。
追问
- Q:DFS 版本? A:三色递归判环。
- Q:重复先修边? A:入度重复累加会失真,需去重或按题意。
02.4.2.2-006 课程表 II(LC 210)怎么输出修课顺序?
一句话结论
Kahn 弹出顺序即一种合法拓扑序;处理数等于课程数返回结果,否则返回空数组;O(V+E) 时间 O(V) 空间。
概念解释
- 弹出序列即顺序。
- 合法:边前置在前。
- 无解返回空。
原理流程
- 零入度入队。
- 弹出加入结果。
- 结果不足 V 返回空。
代码 / 示例
public int[] findOrder(int numCourses, int[][] prereq) {
List<Integer>[] g = new List[numCourses];
int[] indeg = new int[numCourses];
for (int i = 0; i < numCourses; i++) g[i] = new ArrayList<>();
for (int[] p : prereq) { g[p[1]].add(p[0]); indeg[p[0]]++; }
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
int[] res = new int[numCourses];
int idx = 0;
while (!q.isEmpty()) {
int u = q.poll(); res[idx++] = u;
for (int v : g[u]) if (--indeg[v] == 0) q.offer(v);
}
return idx == numCourses ? res : new int[0];
}
常见误区
- 误区:无解仍返回部分顺序;正解:返回空数组。
- 误区:结果下标与弹出顺序错位;正解:idx 同步递增。
追问
- Q:DFS 版本顺序? A:逆后序输出。
- Q:多解哪个对? A:任意合法拓扑序均可。
02.4.2.2-007 拓扑排序什么时候唯一?
一句话结论
任一时刻队列中只有一个零入度顶点,拓扑序唯一;否则多个可并行顶点产生多种顺序;唯一性可作为序列重建类题目的判定条件。
概念解释
- 并行顶点:同层零入度。
- 唯一:每步唯一选择。
- 判定:队列大小恒为 1。
原理流程
- Kahn 每步检查队列。
- 多于一个即多解。
- 全程唯一则序唯一。
代码 / 图示
每步 |queue| == 1 → 唯一
常见误区
- 误区:DAG 拓扑序唯一;正解:通常多解。
- 误区:邻接表顺序决定唯一性;正解:顺序只是输出变体。
追问
- Q:序列重建(LC 444)? A:比较给定序列是否为唯一拓扑序。
- Q:唯一拓扑序对应什么结构? A:顶点间全序约束。
02.4.2.2-008 入度怎么统计?
一句话结论
每条有向边 u→v,indeg[v]++;建图时同步累加;零入度顶点是拓扑起点;有向图统计入度,无向图不分入出度。
概念解释
- 入度:指向该点的边数。
- 加边累加。
- 起点基准。
原理流程
- 初始化入度数组。
- 遍历边集。
- 目标点入度加一。
代码 / 示例
for (int[] e : edges) { g[e[0]].add(e[1]); indeg[e[1]]++; }
常见误区
- 误区:无向边两侧都加入度;正解:无向用度,不分入出。
- 误区:重边重复计入度;正解:按题意去重。
追问
- Q:出度怎么统计? A:邻接表长度即出度。
- Q:入度为 0 一定是起点? A:在 DAG 中是可先排顶点。
02.4.2.2-009 拓扑排序复杂度怎么算?
一句话结论
Kahn 与 DFS 均 O(V+E) 时间:每顶点入队/访问一次,每条边处理一次;辅助 O(V) 存图、入度、队列/栈;结果数组 O(V)。
概念解释
- 顶点一次。
- 边一次降级。
- 辅助线性。
原理流程
- 建图 O(E)。
- 遍历 V+E。
- 标注队列/栈空间。
代码 / 图示
时间 O(V+E)
空间 O(V+E) 存图 + O(V) 队列
常见误区
- 误区:拓扑排序 O(V²);正解:邻接表 O(V+E)。
- 误区:DFS 不计递归栈;正解:O(V) 最坏。
追问
- Q:邻接矩阵拓扑? A:O(V²) 扫邻接。
- Q:大规模图? A:邻接表 + Kahn 迭代。
02.4.2.2-010 DAG 有哪些性质?
一句话结论
DAG 存在拓扑序;存在入度为 0 的顶点;最长路径、关键路径可在拓扑序上 DP;无环是拓扑排序的前提。
概念解释
- 无环。
- 可线性排序。
- 顺序上做 DP。
原理流程
- 拓扑序展开。
- 按序松弛后继。
- 求最长/最短路径。
代码 / 图示
拓扑序 → DP 松弛后继
常见误区
- 误区:DAG 一定连通;正解:可不连通,多分量分别排序。
- 误区:DAG 有环;正解:定义即无环。
追问
- Q:DAG 最长路径? A:拓扑序 DP,O(V+E)。
- Q:关键路径? A:最长路径即工期关键链。
02.4.2.2-011 有向图环检测三色标记怎么用?
一句话结论
白(0)未访问、灰(1)在递归栈、黑(2)已完成;DFS 遇灰节点即回边成环;完成后置黑;区分在栈与已完成是关键。
概念解释
- 三色状态。
- 灰:栈内祖先。
- 黑:处理完。
原理流程
- 进入节点置灰。
- 邻接递归。
- 完成置黑。
代码 / 示例
// 0 白 1 灰 2 黑
常见误区
- 误区:只用布尔 visited;正解:已完成节点的回边不是环。
- 误区:遇黑节点判环;正解:黑是已处理,跳过。
追问
- Q:无向图三色? A:需父节点排除回边。
- Q:环上路径记录? A:灰节点对应栈路径。
02.4.2.2-012 拓扑排序在工程上有哪些应用?
一句话结论
编译依赖(先编译被依赖模块)、课程先修、任务调度、包管理安装顺序、构建系统;环依赖需在构建前检测并报错。
概念解释
- 依赖前置。
- 顺序执行。
- 环依赖阻断。
原理流程
- 依赖建成有向边。
- 拓扑排序出执行序。
- 有环报错。
代码 / 图示
依赖:A 被 B 依赖 → A → B
常见误区
- 误区:依赖方向与边方向相反;正解:先修指向后续。
- 误区:工程允许循环依赖;正解:通常需解环。
追问
- Q:循环依赖怎么解? A:拆分模块、抽公共层,具体按架构。
- Q:并行任务调度? A:同层零入度可并行。
02.4.2.2-013 环上依赖怎么定位与处理?
一句话结论
DFS 记录栈路径,遇灰节点截取栈中该节点到当前路径即环;工程上解环靠调整依赖方向或抽公共模块;算法题只要求判环与输出序。
概念解释
- 环路径:栈内片段。
- 定位:灰节点位置。
- 处理:结构调整。
原理流程
- 栈记录当前路径。
- 遇灰截取环段。
- 报告环上节点。
代码 / 图示
栈:[a, b, c],c → a
环:a → b → c → a
常见误区
- 误区:Kahn 能输出环上节点;正解:Kahn 只判存在,定位用 DFS 栈。
- 误区:环上节点入度为 0;正解:环内互锁。
追问
- Q:强连通分量? A:环的推广,Tarjan/Kosaraju,属进阶。
- Q:自环定位? A:节点邻接含自身。
02.4.2.2-014 多个拓扑序说明什么?
一句话结论
存在可并行的零入度顶点,约束未形成全序;输出任意合法序即可;题目要求唯一序时需额外校验每步队列大小。
概念解释
- 并行:同层可选。
- 多解并存。
- 题目口径。
原理流程
- 队列多顶点。
- 任选弹出。
- 结果均合法。
代码 / 图示
A、B 均零入度 → [A,B] 或 [B,A]
常见误区
- 误区:多解被判错误;正解:合法即可。
- 误区:要求字典序拓扑序;正解:需优先队列按编号选。
追问
- Q:字典序最小拓扑序? A:小顶堆选编号最小。
- Q:拓扑序数量怎么算? A:DP 计数,较复杂。
02.4.2.2-015 拓扑排序有哪些边界用例?
一句话结论
空图、单顶点、无边、全链依赖、多分量、自环、双向边成环、重复边;判空、处理数对比与环判定。
概念解释
- 空与最短。
- 链与分量。
- 环情形。
原理流程
- 空图返回空序。
- 单顶点直接入队。
- 环情形返回无解。
代码 / 图示
n=0 / 单点
链 A→B→C
自环 / 双向
常见误区
- 误区:空课程列表未处理;正解:返回空序。
- 误区:双向边不判环;正解:u→v、v→u 即环。
追问
- Q:无边图拓扑序? A:任意顶点排列均合法。
- Q:重复先修边? A:入度去重后统计。
02.4.2.2-016 Kahn 与 DFS 拓扑怎么选型?
一句话结论
需要边处理顺序、判环与输出顺序直观选 Kahn;需要后序信息或结合 DFS 框架选 DFS;两者时间同阶;大规模深图优先 Kahn 迭代避免爆栈。
概念解释
- Kahn:入度驱动。
- DFS:后序逆序。
- 实现稳定性。
原理流程
- 看是否依赖入度统计。
- 看递归深度风险。
- 选算法。
代码 / 图示
直观判环/输出:Kahn
DFS 体系:后序逆序
常见误区
- 误区:DFS 拓扑不需要判环;正解:三色同时检测。
- 误区:Kahn 结果是逆后序;正解:弹出序即正拓扑序。
追问
- Q:Kahn 队列顺序影响合法性吗? A:不影响合法性。
- Q:深图递归栈溢出? A:改 Kahn 或迭代 DFS。
02.4.2.2-017 邻接表与入度数组怎么配合?
一句话结论
邻接表存 u → 邻接点 供遍历降级;入度数组存每点前置数;加边时同时建表与累加入度;弹出 u 时遍历 g[u] 降级后继入度。
概念解释
- 表:出边。
- 入度:前置计数。
- 配合更新。
原理流程
- 加边:建表 + 入度++。
- 零入度入队。
- 出边降级入度。
代码 / 图示
g[u]: 邻接后继
indeg[v]: 前置数
常见误区
- 误区:只建表不统计入度;正解:Kahn 依赖入度。
- 误区:降级时改错数组;正解:后继入度减一。
追问
- Q:加权图影响拓扑吗? A:不影响,权值另存。
- Q:入度数组被修改后无法复用? A:需要统计可先备份。
02.4.2.2-018 拓扑题常见错误有哪些?
一句话结论
边方向反向、入度漏加、结果数未对比判环、DFS 前序加入未反转、遇已完成节点误判环、多分量未枚举;按建图、判环、输出三步复核。
概念解释
- 方向。
- 计数。
- 状态口径。
原理流程
- 复核边方向。
- 对比处理数。
- 检查状态标记。
代码 / 图示
建图 → 入度 → 弹出降级 → 结果对比
常见误区
- 误区:先修关系边写反;正解:先修 → 后修。
- 误区:DFS 结果未反转;正解:后序列表逆序。
追问
- Q:怎么自查方向? A:画两节点依赖图对照。
- Q:判环漏检? A:结果数与 V 对比。
02.4.2.2-019 拓扑排序复杂度怎么汇报?
一句话结论
时间 O(V+E),存图 O(V+E),辅助 O(V);DFS 递归栈最坏 O(V),Kahn 队列最坏 O(V);结果数组 O(V);邻接矩阵实现退化为 O(V²)。
概念解释
- 线性于顶点边数。
- 辅助按顶点。
- 存储按表示。
原理流程
- 标注图规模。
- 每点边处理一次。
- 分列时间空间。
代码 / 图示
邻接表:O(V+E) / O(V+E) 存图
递归栈:O(V)
常见误区
- 误区:拓扑排序空间 O(1);正解:存图与队列 O(V)。
- 误区:DFS 递归不算空间;正解:栈 O(V)。
追问
- Q:边权影响复杂度吗? A:不影响遍历量级。
- Q:超大图内存? A:邻接表分片/流式处理。
02.4.2.2-020 拓扑与环检测常见变体有哪些?
一句话结论
课程表可修/顺序、序列重建唯一性、DAG 最长路径关键路径、编译依赖、环上节点定位;主线是入度统计或三色 DFS,按要求补顺序/判环/DP。
概念解释
- 框架:Kahn/DFS。
- 附加:唯一性、最长路径。
- 场景变体。
原理流程
- 选 Kahn 或 DFS。
- 判环出序。
- 按题补唯一性或 DP。
代码 / 图示
判环:处理数/三色
出序:弹出序/逆后序
关键路径:序上 DP
常见误区
- 误区:变体题重新发明遍历;正解:复用拓扑框架。
- 误区:关键路径在环图上跑;正解:先确认 DAG。
追问
- Q:DAG 最长路径怎么 DP? A:按拓扑序松弛
dp[v]=max(dp[v], dp[u]+w)。 - Q:强连通分量与环区别? A:环是 SCC 的特例概念。