4. 拓扑排序实战：Kahn算法实现、DFS实现拓扑排序、检测环的存在

拓扑排序，说白了就是给DAG里的节点排个队。排队的规则很简单：如果A依赖B，那B必须站在A前面。这个顺序在任务编排里太重要了——你总不能让一个任务在它的依赖还没完成时就跑起来吧？

我刚开始接触拓扑排序时，觉得这东西不就是个排序嘛，能有多复杂？直到有一次在线上调度系统里，一个隐藏的环导致整个任务队列死锁，所有worker都在空转……嗯，从那以后我再也不敢小看拓扑排序和环检测了。

4.1 Kahn算法：基于入度的贪心策略

Kahn算法的思路非常直观。你想想看，一个节点如果没有入度（也就是没有前置依赖），那它就可以直接执行了。我们不断把这些“自由节点”摘出来，然后更新剩余节点的入度，重复这个过程直到所有节点都被处理完。

具体步骤是这样的：

1. 统计每个节点的入度（有多少条边指向它）
2. 把所有入度为0的节点加入队列
3. 从队列中取出一个节点，把它加入拓扑序列
4. 遍历这个节点的所有后继节点，把它们的入度减1
5. 如果某个后继节点的入度变成0，就把它加入队列
6. 重复步骤3-5，直到队列为空

如果最终拓扑序列里的节点数不等于总节点数，说明图里有环。

// Kahn算法实现 - Java版本
public List<Integer> topologicalSortKahn(int n, int[][] edges) {
    // 构建邻接表和入度数组
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        int from = edge[0], to = edge[1];
        graph.get(from).add(to);
        inDegree[to]++;
    }

    // 入度为0的节点入队
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        for (int neighbor : graph.get(node)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }

    // 检测环：如果结果长度不等于节点数，说明有环
    if (result.size() != n) {
        throw new RuntimeException("图中存在环，无法进行拓扑排序");
    }
    return result;
}

4.2 DFS实现拓扑排序：后序遍历的妙用

DFS版本的拓扑排序，核心思想是后序遍历。你从某个节点出发，沿着有向边一直往下走，直到走不动了再回头。在回头的过程中，把节点加入结果列表。最后把结果反转一下，就是拓扑序列。

为什么会这样？因为后序遍历保证了：一个节点在它的所有后继节点都被访问完之后，才会被加入列表。反转之后，这个节点就排在了所有后继节点的前面——这不就是拓扑排序的要求吗？

// DFS实现拓扑排序 - Java版本
public List<Integer> topologicalSortDFS(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
    }

    // 0=未访问, 1=正在访问, 2=已访问完成
    int[] visited = new int[n];
    List<Integer> result = new ArrayList<>();
    boolean[] hasCycle = {false};

    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
            dfs(i, graph, visited, result, hasCycle);
        }
    }

    if (hasCycle[0]) {
        throw new RuntimeException("图中存在环，无法进行拓扑排序");
    }

    // 后序遍历结果反转得到拓扑序列
    Collections.reverse(result);
    return result;
}

private void dfs(int node, List<List<Integer>> graph,
                 int[] visited, List<Integer> result, boolean[] hasCycle) {
    visited[node] = 1; // 标记为正在访问

    for (int neighbor : graph.get(node)) {
        if (visited[neighbor] == 1) {
            // 遇到了正在访问中的节点，说明有环
            hasCycle[0] = true;
            return;
        }
        if (visited[neighbor] == 0) {
            dfs(neighbor, graph, visited, result, hasCycle);
        }
    }

    visited[node] = 2; // 标记为已访问完成
    result.add(node);  // 后序加入结果
}

4.3 环检测：两种算法的共同使命

不管是Kahn还是DFS，环检测都是它们的内置功能。我来对比一下两种检测方式：

对比维度	Kahn算法	DFS算法
检测原理	最终节点数 < 总节点数	遇到正在访问中的节点
时间复杂度	O(V+E)	O(V+E)
空间复杂度	O(V)	O(V)（递归栈）
能否定位环	只能判断有无，不能定位	可以记录环的路径
并行友好	是（队列天然支持）	否（递归串行）

我曾经在一个数据管道项目里遇到过这样的情况：一个环导致整个ETL流程卡死，所有下游任务都在等一个永远不会完成的上游任务。用DFS的环检测功能，我很快就定位到了环的路径——原来是两个任务互相依赖，形成了一个死循环。

4.4 两种算法的选择策略

在实际项目中，我一般这样选：

• 需要并行执行 → 选Kahn。队列里的节点天然可以并发。
• 需要定位环 → 选DFS。它能告诉你环的具体路径。
• 图特别大 → 选Kahn。避免递归栈溢出。
• 需要动态更新 → 选Kahn。入度信息容易维护。

4.5 知识体系总览

下面这张图把本章的核心逻辑串起来了：

4.6 避坑指南

最后分享几个我踩过的坑：

• 入度数组别搞反了——入度是指向节点的边数，不是从节点出发的边数。我见过有人把入度和出度搞混，结果拓扑序列完全反了。
• DFS的递归深度——如果图有几千层依赖，递归栈会爆。我建议设置一个最大深度限制，或者直接用迭代版本。
• 多线程环境下的环检测——如果多个线程同时修改图结构，环检测的结果可能不准确。需要加锁或者使用快照。
• 空图和单节点图——这两种情况都是合法的DAG，拓扑排序就是节点本身。别忘记处理边界情况。