罗罗编程学习记录
本页内容 展开查看

02.4.2.2 拓扑排序与环检测

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.2 图论与并查集

02.4.2.2-001 什么是拓扑排序?

一句话结论

对有向无环图(DAG)排出顶点线性序,使每条有向边 u→v 中 u 排在 v 前;用于依赖任务排序;存在环则无拓扑序。

概念解释

  • DAG:有向无环。
  • 依赖前置:边指向后继。
  • 线性序满足先后。

原理流程

  1. 确认无环。
  2. 入度清零者先排。
  3. 移除该顶点更新入度。

代码 / 图示

A → B → C
拓扑序:A, B, C

常见误区

  • 误区:任何图都能拓扑排序;正解:有环无解。
  • 误区:拓扑序唯一;正解:通常有多解。

追问

  • Q:拓扑序用途? A:编译依赖、课程先修、任务调度。
  • Q:环存在时输出什么? A:无解/空序列。

02.4.2.2-002 Kahn 算法怎么做?

一句话结论

统计各顶点入度,入度为 0 入队;弹出一个加入结果,其邻接点入度减一,减到 0 入队;结果数等于 V 即无环;O(V+E) 时间 O(V) 队列。

概念解释

  • 入度:前置依赖数。
  • 零入度可先做。
  • 移除解锁后继。

原理流程

  1. 建图统计入度。
  2. 零入度入队。
  3. 循环弹出并降级邻接。

代码 / 示例

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) 递归栈。

概念解释

  • 后序:子节点先完成。
  • 逆序:父在前。
  • 环检测三色。

原理流程

  1. 枚举未访问节点 DFS。
  2. 邻接递归完再加入列表。
  3. 列表反转得拓扑序。

代码 / 示例

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。
  • 三色在栈判定。
  • 两种判环口径。

原理流程

  1. Kahn 统计处理数。
  2. 不足 V 即环。
  3. 或 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) 时间。

概念解释

  • 边:先修指向后续。
  • 环:循环依赖。
  • 可完成 = 无环。

原理流程

  1. 建图统计入度。
  2. Kahn 处理全部课程。
  3. 处理数等于课程数返回 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) 空间。

概念解释

  • 弹出序列即顺序。
  • 合法:边前置在前。
  • 无解返回空。

原理流程

  1. 零入度入队。
  2. 弹出加入结果。
  3. 结果不足 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。

原理流程

  1. Kahn 每步检查队列。
  2. 多于一个即多解。
  3. 全程唯一则序唯一。

代码 / 图示

每步 |queue| == 1 → 唯一

常见误区

  • 误区:DAG 拓扑序唯一;正解:通常多解。
  • 误区:邻接表顺序决定唯一性;正解:顺序只是输出变体。

追问

  • Q:序列重建(LC 444)? A:比较给定序列是否为唯一拓扑序。
  • Q:唯一拓扑序对应什么结构? A:顶点间全序约束。

02.4.2.2-008 入度怎么统计?

一句话结论

每条有向边 u→v,indeg[v]++;建图时同步累加;零入度顶点是拓扑起点;有向图统计入度,无向图不分入出度。

概念解释

  • 入度:指向该点的边数。
  • 加边累加。
  • 起点基准。

原理流程

  1. 初始化入度数组。
  2. 遍历边集。
  3. 目标点入度加一。

代码 / 示例

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)。

概念解释

  • 顶点一次。
  • 边一次降级。
  • 辅助线性。

原理流程

  1. 建图 O(E)。
  2. 遍历 V+E。
  3. 标注队列/栈空间。

代码 / 图示

时间 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。

原理流程

  1. 拓扑序展开。
  2. 按序松弛后继。
  3. 求最长/最短路径。

代码 / 图示

拓扑序 → DP 松弛后继

常见误区

  • 误区:DAG 一定连通;正解:可不连通,多分量分别排序。
  • 误区:DAG 有环;正解:定义即无环。

追问

  • Q:DAG 最长路径? A:拓扑序 DP,O(V+E)。
  • Q:关键路径? A:最长路径即工期关键链。

02.4.2.2-011 有向图环检测三色标记怎么用?

一句话结论

白(0)未访问、灰(1)在递归栈、黑(2)已完成;DFS 遇灰节点即回边成环;完成后置黑;区分在栈与已完成是关键。

概念解释

  • 三色状态。
  • 灰:栈内祖先。
  • 黑:处理完。

原理流程

  1. 进入节点置灰。
  2. 邻接递归。
  3. 完成置黑。

代码 / 示例

// 0 白 1 灰 2 黑

常见误区

  • 误区:只用布尔 visited;正解:已完成节点的回边不是环。
  • 误区:遇黑节点判环;正解:黑是已处理,跳过。

追问

  • Q:无向图三色? A:需父节点排除回边。
  • Q:环上路径记录? A:灰节点对应栈路径。

02.4.2.2-012 拓扑排序在工程上有哪些应用?

一句话结论

编译依赖(先编译被依赖模块)、课程先修、任务调度、包管理安装顺序、构建系统;环依赖需在构建前检测并报错。

概念解释

  • 依赖前置。
  • 顺序执行。
  • 环依赖阻断。

原理流程

  1. 依赖建成有向边。
  2. 拓扑排序出执行序。
  3. 有环报错。

代码 / 图示

依赖:A 被 B 依赖 → A → B

常见误区

  • 误区:依赖方向与边方向相反;正解:先修指向后续。
  • 误区:工程允许循环依赖;正解:通常需解环。

追问

  • Q:循环依赖怎么解? A:拆分模块、抽公共层,具体按架构。
  • Q:并行任务调度? A:同层零入度可并行。

02.4.2.2-013 环上依赖怎么定位与处理?

一句话结论

DFS 记录栈路径,遇灰节点截取栈中该节点到当前路径即环;工程上解环靠调整依赖方向或抽公共模块;算法题只要求判环与输出序。

概念解释

  • 环路径:栈内片段。
  • 定位:灰节点位置。
  • 处理:结构调整。

原理流程

  1. 栈记录当前路径。
  2. 遇灰截取环段。
  3. 报告环上节点。

代码 / 图示

栈:[a, b, c],c → a
环:a → b → c → a

常见误区

  • 误区:Kahn 能输出环上节点;正解:Kahn 只判存在,定位用 DFS 栈。
  • 误区:环上节点入度为 0;正解:环内互锁。

追问

  • Q:强连通分量? A:环的推广,Tarjan/Kosaraju,属进阶。
  • Q:自环定位? A:节点邻接含自身。

02.4.2.2-014 多个拓扑序说明什么?

一句话结论

存在可并行的零入度顶点,约束未形成全序;输出任意合法序即可;题目要求唯一序时需额外校验每步队列大小。

概念解释

  • 并行:同层可选。
  • 多解并存。
  • 题目口径。

原理流程

  1. 队列多顶点。
  2. 任选弹出。
  3. 结果均合法。

代码 / 图示

A、B 均零入度 → [A,B] 或 [B,A]

常见误区

  • 误区:多解被判错误;正解:合法即可。
  • 误区:要求字典序拓扑序;正解:需优先队列按编号选。

追问

  • Q:字典序最小拓扑序? A:小顶堆选编号最小。
  • Q:拓扑序数量怎么算? A:DP 计数,较复杂。

02.4.2.2-015 拓扑排序有哪些边界用例?

一句话结论

空图、单顶点、无边、全链依赖、多分量、自环、双向边成环、重复边;判空、处理数对比与环判定。

概念解释

  • 空与最短。
  • 链与分量。
  • 环情形。

原理流程

  1. 空图返回空序。
  2. 单顶点直接入队。
  3. 环情形返回无解。

代码 / 图示

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:后序逆序。
  • 实现稳定性。

原理流程

  1. 看是否依赖入度统计。
  2. 看递归深度风险。
  3. 选算法。

代码 / 图示

直观判环/输出:Kahn
DFS 体系:后序逆序

常见误区

  • 误区:DFS 拓扑不需要判环;正解:三色同时检测。
  • 误区:Kahn 结果是逆后序;正解:弹出序即正拓扑序。

追问

  • Q:Kahn 队列顺序影响合法性吗? A:不影响合法性。
  • Q:深图递归栈溢出? A:改 Kahn 或迭代 DFS。

02.4.2.2-017 邻接表与入度数组怎么配合?

一句话结论

邻接表存 u → 邻接点 供遍历降级;入度数组存每点前置数;加边时同时建表与累加入度;弹出 u 时遍历 g[u] 降级后继入度。

概念解释

  • 表:出边。
  • 入度:前置计数。
  • 配合更新。

原理流程

  1. 加边:建表 + 入度++。
  2. 零入度入队。
  3. 出边降级入度。

代码 / 图示

g[u]: 邻接后继
indeg[v]: 前置数

常见误区

  • 误区:只建表不统计入度;正解:Kahn 依赖入度。
  • 误区:降级时改错数组;正解:后继入度减一。

追问

  • Q:加权图影响拓扑吗? A:不影响,权值另存。
  • Q:入度数组被修改后无法复用? A:需要统计可先备份。

02.4.2.2-018 拓扑题常见错误有哪些?

一句话结论

边方向反向、入度漏加、结果数未对比判环、DFS 前序加入未反转、遇已完成节点误判环、多分量未枚举;按建图、判环、输出三步复核。

概念解释

  • 方向。
  • 计数。
  • 状态口径。

原理流程

  1. 复核边方向。
  2. 对比处理数。
  3. 检查状态标记。

代码 / 图示

建图 → 入度 → 弹出降级 → 结果对比

常见误区

  • 误区:先修关系边写反;正解:先修 → 后修。
  • 误区: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²)。

概念解释

  • 线性于顶点边数。
  • 辅助按顶点。
  • 存储按表示。

原理流程

  1. 标注图规模。
  2. 每点边处理一次。
  3. 分列时间空间。

代码 / 图示

邻接表: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。
  • 附加:唯一性、最长路径。
  • 场景变体。

原理流程

  1. 选 Kahn 或 DFS。
  2. 判环出序。
  3. 按题补唯一性或 DP。

代码 / 图示

判环:处理数/三色
出序:弹出序/逆后序
关键路径:序上 DP

常见误区

  • 误区:变体题重新发明遍历;正解:复用拓扑框架。
  • 误区:关键路径在环图上跑;正解:先确认 DAG。

追问

  • Q:DAG 最长路径怎么 DP? A:按拓扑序松弛 dp[v]=max(dp[v], dp[u]+w)。
  • Q:强连通分量与环区别? A:环是 SCC 的特例概念。