拓扑排序算法
给一堆“任务”或者说“节点”排个队。什么队呢？一个有向无环图（DAG, Directed Acyclic Graph）中，所有节点的线性序列。
这个序列有个硬性要求：如果图中有一条从 A 到 B 的边，那么在排好的队里，A 必须在 B 的前面。
说人话就是，你大学选课，想学《算法进阶》，就必须先学《数据结构》。这个先后顺序，就是拓扑序。想编译代码，得先把依赖的库给编译了。这个编译顺序，也是拓扑序。所以，只要看到问题里有“依赖关系”、“先后顺序”、“前提条件”这类词，脑子里就得把“拓扑排序”这四个大字给我亮起来。
还有一个关键点：只有有向无环图（DAG）才有拓扑排序。你想想，如果 A 依赖 B，B 又依赖 A，这不就死锁了吗？谁都别想先开始。所以，如果图里有环，那就没法排，直接告诉面试官：“这事儿办不成！”。
好，背景聊完，上题。通常题目会这么给你：
给定一个整数
numCourses，代表课程总数，从0到numCourses-1。再给你一个数组prerequisites，其中prerequisites[i] = [ai, bi]表示若想学习课程ai，你必须先学习课程bi。请你返回一个可行的课程学习顺序。如果无法完成所有课程，则返回一个空数组。
这不就是拓扑排序的裸题吗？别慌，咱们从最直观的思路开始，一步步把它拿下。
解法一：广度优先搜索 (BFS) - 俗称“剥洋葱法”
我觉得这是最符合直觉的一种思路。咱们想啊，要安排一个学习顺序，最先能学的是什么课？肯定是那些没有任何先修课要求的课，对吧？
这在图里怎么表示？就是一个节点的入度（in-degree）为 0。
这个思路就很自然了：
先把所有入度为 0 的节点（课程）找出来，它们是第一批可以学习的。
把这些课学完，然后呢？是不是有一些原本需要这些课作为先修课的后续课程，现在它们的“前置条件”就满足了一个？
对，学完一门课
A，所有依赖A的课程B、C、D，它们的入度就可以减 1。在减 1 的过程中，如果发现课程
B的入度也变成 0 了，那说明B的所有先修课都学完了，它就成了下一批可以学习的课程。我们不断重复这个过程：找到入度为 0 的课 -> 学掉 -> 更新后续课程的入度 -> 找到新的入度为 0 的课... 直到所有课程都学完。
这个过程，像不像一层一层剥洋葱？每次都把最外层（入度为0）的剥掉，露出新的一层。
怎么用数据结构实现这个“剥洋葱”的过程呢？
一个数组
inDegree记录每个节点的入度。一个队列
queue存放所有当前入度为 0 的节点。一个邻接表
graph存储图的结构，方便我们找到一个节点的所有后继节点。
具体流程：
建图和统计入度：遍历
prerequisites，构建邻接表graph，同时填充inDegree数组。初始化队列：遍历所有课程，把
inDegree为 0 的课程全部扔进队列queue。BFS循环：
当队列不为空时，出队一个课程
c。将
c加入结果列表。遍历
c的所有后继课程next_c（通过邻接表）。将
next_c的入度减 1。如果
next_c的入度减为 0，说明它的前置条件都满足了，将其入队。
检查结果：循环结束后，检查结果列表中的课程数量是否等于总课程数
numCourses。如果相等，说明所有课程都学完了，返回结果；如果不等，说明图里有环，有些课程的入度永远无法变为 0，就没法入队，所以返回空数组。
这个方法也叫Kahn算法，听着高大上，其实就是这个朴素的道理。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 1. 构建邻接表和入度数组
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
int[] inDegree = new int[numCourses];
for (int[] p : prerequisites) {
// p[1] -> p[0], 即学 p[0] 之前要先学 p[1]
graph.get(p[1]).add(p[0]);
inDegree[p[0]]++;
}
// 2. 将所有入度为0的节点入队
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int[] result = new int[numCourses];
int count = 0; // 记录已修课程的数量
// 3. BFS过程
while (!queue.isEmpty()) {
int currentCourse = queue.poll();
result[count++] = currentCourse;
// 遍历当前课程的后继课程
for (int nextCourse : graph.get(currentCourse)) {
inDegree[nextCourse]--;
// 如果后继课程的入度变为0，则入队
if (inDegree[nextCourse] == 0) {
queue.offer(nextCourse);
}
}
}
// 4. 检查是否所有课程都已修完
if (count == numCourses) {
return result;
}
return new int[0]; // 存在环，无法完成
}
}
解法二：深度优先搜索 (DFS) - 逆向思维的产物
BFS是从“起点”开始，找入度为0的。那DFS呢？咱们可以换个角度想。
最终排好序的列表，排在最后面的课程应该是什么样的？
它应该没有任何后继课程，或者说它的后继课程都已经排在它后面了。说白了，它不作为任何其他课程的先修课。在图里，就是出度为 0 的节点。
这启发我们，可以从任意一个节点开始，做深度优先搜索，一直搜到底（搜到出度为0的节点）。这个“底”，就是拓扑序中比较靠后的节点。
这个过程有点像递归的“归”过程。
我们从一个节点
A开始DFS。A依赖B，B依赖C。我们的搜索路径是A -> B -> C。当搜到
C时，发现C没有依赖任何其他节点了，它已经走到了“底”。好，我们把C记录下来。然后回溯到
B，B的所有依赖（只有C）都已经被访问并记录过了。说明B这条路也走完了，我们记录下B。同理，回溯到
A，记录下A。
你看，我们记录的顺序是 C, B, A。而真正的拓扑序是 A -> B -> C。所以，DFS的后序遍历结果，反转一下，就是拓扑排序的结果。是不是有点意思？
但是！别忘了环。DFS怎么判断有环？
如果在DFS的路径上，你从节点 A 出发，走着走着，又回到了 A，那就有环了。所以我们需要一个标记来记录当前这次DFS“正在访问”的节点。
我们需要三种状态来标记一个节点：
0(UNVISITED): 还没访问过。1(VISITING): 正在访问。说白了，这个节点在当前的递归栈里。2(VISITED): 已访问过。这个节点以及它的所有后续节点都已经被彻底访问完了。
DFS流程：
建图：只需要邻接表
graph。状态数组
visited：初始化所有节点状态为0。结果栈
stack：用一个栈来存储后序遍历的结果，栈顶到栈底就是拓扑序。主循环：遍历所有课程，如果课程状态为
0，就从它开始进行DFS。DFS函数
dfs(course)：将
course的状态置为1(VISITING)。遍历
course的所有后继课程next_c：如果
next_c的状态是0，递归调用dfs(next_c)。如果递归返回有环，直接一路返回有环。如果
next_c的状态是1，说明在当前路径上又遇到了这个点，发现环！，直接返回有环。如果
next_c的状态是2，说明它已经被别的路径访问完了，是安全的，跳过。
如果循环正常结束，说明
course的所有后继都访问完了。将
course的状态置为2(VISITED)。将
course压入栈中。返回无环。
检查结果：如果在主循环中任何一次
dfs调用返回了有环，则拓扑排序失败。否则，将栈中的元素依次弹出，就是最终结果。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] p : prerequisites) {
graph.get(p[1]).add(p[0]);
}
// 0: unvisited, 1: visiting, 2: visited
int[] visited = new int[numCourses];
Deque<Integer> stack = new ArrayDeque<>(); // 用栈来存储后序遍历结果
for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0) {
if (hasCycle(i, graph, visited, stack)) {
// 如果有环，直接返回空数组
return new int[0];
}
}
}
int[] result = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
result[i] = stack.pop();
}
return result;
}
private boolean hasCycle(int course, List<List<Integer>> graph, int[] visited, Deque<Integer> stack) {
visited[course] = 1; // 标记为正在访问
for (int nextCourse : graph.get(course)) {
if (visited[nextCourse] == 0) {
if (hasCycle(nextCourse, graph, visited, stack)) {
return true;
}
} else if (visited[nextCourse] == 1) {
// 在当前递归路径上再次遇到，说明有环
return true;
}
}
visited[course] = 2; // 标记为已访问
stack.push(course); // 入栈
return false;
}
}
解法三：DFS的另一种实现 - 使用两个Set
上面那个三状态的DFS是标准写法，但有时候用 Set 来实现可能更清晰，能帮你更深刻地理解“当前路径”和“已访问”的区别。这个解法本质和解法二是一样的，只是换了数据结构，算是对思维的一个拓展。
visitedSet: 存所有已访问过的节点（对应状态2）。作用是剪枝，如果一个节点已经确认无环并且处理完毕，就没必要再从它开始走一遍DFS了。onPathSet: 存当前递归路径上的节点（对应状态1）。它的作用就是检测环。
DFS流程 (Set版本):
建图。
初始化
visited和onPath两个HashSet，以及结果栈stack。主循环遍历所有课程，如果课程不在
visited里，则对其dfs。DFS函数
dfs(course)：将
course加入onPath和visited。遍历其邻居
next_c:如果
next_c在onPath中，说明有环，返回true。如果
next_c不在visited里，对其递归dfs，如果递归返回有环，也返回true。
回溯：将
course从onPath中移除。这是关键，因为当course的递归调用结束时，它就不在“当前路径”上了。将
course压栈。返回无环 (
false)。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] p : prerequisites) {
graph.get(p[1]).add(p[0]);
}
Set<Integer> visited = new HashSet<>(); // 存已访问过的节点
Set<Integer> onPath = new HashSet<>(); // 存当前递归路径上的节点
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (!visited.contains(i)) {
if (hasCycle(i, graph, visited, onPath, stack)) {
return new int[0];
}
}
}
int[] result = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
result[i] = stack.pop();
}
return result;
}
private boolean hasCycle(int course, List<List<Integer>> graph, Set<Integer> visited, Set<Integer> onPath, Deque<Integer> stack) {
visited.add(course);
onPath.add(course);
for (int nextCourse : graph.get(course)) {
if (onPath.contains(nextCourse)) {
return true; // 发现环
}
if (!visited.contains(nextCourse)) {
if (hasCycle(nextCourse, graph, visited, onPath, stack)) {
return true;
}
}
}
onPath.remove(course); // 回溯
stack.push(course);
return false;
}
}
这个版本和三状态数组的版本在逻辑上是等价的，但 Set 的 add, contains, remove 操作语义更明确，有时写起来更舒服。
总结一下
咱们今天聊了拓扑排序的两种主流思路，三种实现：
BFS (Kahn算法)：正向思维，像剥洋葱。从入度为0的节点开始，一层层向外扩展。实现起来是迭代，比较好理解。
DFS：逆向思维，像探险。深入到最底层（没有出度），然后回溯时记录路径。记录顺序和拓扑序是反的，所以要倒序输出。实现上是递归，关键在于用三种状态（或两个Set）来正确地检测环。
这两个方法时间复杂度都是 O(V+E)，V是顶点数，E是边数，因为每个节点和每条边都只访问一次。空间复杂度也是 O(V+E)，用于存储图、队列/栈、以及状态数组。