什么是拓扑排序？Kahn 算法和 DFS 怎么实现？

简化版

拓扑排序是对有向无环图（DAG） 的顶点排成一个线性序列，使得每条边 u→v 都满足 u 排在 v 前面（先做的排前面）。它解决「有依赖关系的任务该按什么顺序做」的问题。两种实现：Kahn 算法（BFS） ——反复取出入度为 0 的节点；DFS ——后序遍历再逆序。只有 DAG 才能拓扑排序，有环就排不出来（正好可用来判环）。

详细版

前提：有向无环图（DAG）。目标：线性序列中，所有边都「从前指向后」。

Kahn 算法（BFS，基于入度）

List<Integer> topoSort(int n, List<List<Integer>> adj) {
    int[] indeg = new int[n];
    for (var list : adj) for (int v : list) indeg[v]++;   // 统计入度
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i); // 入度0入队
    List<Integer> res = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll(); res.add(u);
        for (int v : adj.get(u))
            if (--indeg[v] == 0) q.offer(v);   // 移除 u 后，邻居入度减一，变0则入队
    }
    return res.size() == n ? res : new ArrayList<>(); // 数量不足 n → 有环
}

DFS 算法

对每个节点 DFS，在递归返回时（后序） 把节点压栈；最后逆序输出栈就是拓扑序。因为一个节点的所有后继都处理完了它才入栈，所以逆序后它排在后继前面。

完整版教学

一、拓扑排序解决什么问题

现实中很多任务有先后依赖：选课有先修课、编译有模块依赖、项目有前置任务、Excel 单元格有计算依赖。拓扑排序就是把这些「谁必须在谁之前」的约束，理成一个可执行的线性顺序。它的前提是依赖关系不能成环——如果 A 依赖 B、B 又依赖 A，就是死循环，无解。所以拓扑排序只对有向无环图（DAG） 成立。

二、Kahn 算法：不断摘掉「没有前置」的节点

Kahn 算法的直觉非常朴素：入度为 0 的节点，就是当前没有任何前置依赖、可以马上做的任务。

统计每个节点的入度（有多少条边指向它）。
把所有入度为 0 的节点入队（它们能立刻执行）。
每次取出一个节点加入结果，然后把它的所有后继的入度减 1（相当于「这个前置任务做完了」）——某个后继入度变 0，说明它的前置都做完了，入队。
重复，直到队列空。

如果最终排出的节点数 = 总节点数，成功；如果少于总数，说明剩下的节点入度始终 > 0，它们互相依赖成环——这正是用拓扑排序判环的原理。

三、DFS 算法：后序逆序

DFS 版利用一个性质：在 DFS 后序（递归返回）时，一个节点的所有可达后继都已经处理完了。所以在返回时把节点压栈，最后逆序输出，就保证每个节点都排在它的后继之前。要注意配合环检测（三色标记），有环时无法得到合法拓扑序。

四、拓扑序不唯一

一个 DAG 的拓扑排序通常不唯一。因为同一时刻可能有多个入度为 0 的节点（多个任务都没有前置），它们之间的先后可以任意。比如「穿袜子」和「穿裤子」都不依赖别的，谁先谁后都行。题目如果要求特定顺序（如字典序最小），可以把 Kahn 里的普通队列换成优先队列。

五、复杂度与应用

时间 O(V + E)：每个节点、每条边各处理一次。
空间 O(V)：入度数组 + 队列。
应用：课程表 / 选课顺序、任务调度、编译依赖（Makefile、构建工具）、包管理器的安装顺序、Excel 公式重算、死锁检测（资源依赖成环即死锁）。

六、常见误区与追问

考点	正确口径
适用对象	有向无环图 DAG
Kahn	不断取入度为 0 的点
DFS	后序加入结果，最后反转

Kahn:
queue all indegree-0 nodes
while queue:
  u = poll
  for v in out[u]:
    if --indegree[v] == 0: offer(v)

拓扑排序排的是依赖顺序：前置任务必须出现在后置任务之前。

误区：无向图也可以做拓扑排序。 拓扑排序针对有向依赖关系，无向边没有前后方向。
误区：有环图也能给出完整拓扑序。 环意味着互相依赖，无法让所有边都满足先后顺序。
误区：拓扑序唯一。 只要某一时刻有多个入度为 0 的点，就可能产生不同但都合法的拓扑序。
追问：Kahn 如何判环？ 如果最终输出节点数小于 V，说明还有节点入度无法降为 0，图中有环。
追问：DFS 为什么后序反转？ 一个节点的后继都处理完后再加入结果，反转后前驱就会排在后继前面。
追问：典型应用有哪些？ 课程安排、构建依赖、任务调度、编译顺序等都可建模为拓扑排序。

七、加强记忆

拓扑排序把 DAG 的顶点排成线性序，使每条边 u→v 都满足 u 在 v 前（依赖在前）。Kahn（BFS）：反复取入度为 0 的节点、移除后邻居入度减 1，排出数 < 总数则有环。DFS：后序压栈再逆序。拓扑序不唯一（要字典序最小用优先队列）。O(V+E)。应用：选课、任务调度、编译依赖、死锁检测。只有无环才能排——正好用来判环。

简化版

详细版