每日算法 — 使用java实现拓扑排序：Kahn算法与DFS后序遍历的DAG线性化

算法引入

在现实世界中，许多任务之间存在先后顺序的依赖关系：编译程序时需要先编译依赖库才能编译主程序，课程学习需要先修完前置课程才能选后续课程，项目管理中某些任务必须在其他任务完成后才能开始。这些依赖关系可以用有向无环图（DAG, Directed Acyclic Graph）来建模，而拓扑排序就是将DAG中的所有节点排成一个线性序列，使得对于图中的每一条有向边 $(u, v)$，节点 $u$ 在序列中都出现在 $v$ 之前。

拓扑排序是图论中最实用的算法之一，它揭示了一个DAG中隐含的”先后次序”，广泛应用于任务调度、编译系统、数据流处理等场景。

核心思想

拓扑排序有两大经典实现思路：

Kahn算法（BFS-based）：
– 反复寻找并移除图中入度为0的节点（没有前置依赖的节点）
– 移除节点时，将其所有邻接节点的入度减1
– 若某邻接节点入度变为0，说明其所有前置依赖已满足，加入待处理队列
– 最终若所有节点都被移除，则得到一个合法的拓扑序列；若剩余节点入度均大于0，则图中存在环

DFS后序遍历法：
– 对图进行深度优先搜索
– 当某节点的所有邻接节点都已访问完毕（即递归返回时），将该节点加入结果列表前端
– 利用递归调用栈的自然”后进先出”特性，确保子节点先于父节点入序列
– 若DFS过程中遇到已访问但未完成的节点，说明存在环

完整Java实现

import java.util.*;

/**
 * 拓扑排序（Topological Sort）实现
 * 提供Kahn算法（BFS）和DFS后序遍历两种实现
 * 适用于任务调度、编译依赖、课程规划等场景
 */
public class TopologicalSort {

    /** 图的邻接表表示 */
    private final Map<Integer, List<Integer>> adjacencyList;
    /** 节点数量 */
    private final int numNodes;

    public TopologicalSort(int numNodes) {
        this.numNodes = numNodes;
        this.adjacencyList = new HashMap<>();
        for (int i = 0; i < numNodes; i++) {
            adjacencyList.put(i, new ArrayList<>());
        }
    }

    /**
     * 添加有向边 u -> v
     * 表示任务u必须在任务v之前完成
     *
     * @param u 前置节点
     * @param v 后置节点
     */
    public void addEdge(int u, int v) {
        adjacencyList.get(u).add(v);
    }

    /**
     * Kahn算法实现拓扑排序（基于BFS）
     * 核心思想：反复移除入度为0的节点
     *
     * @return 拓扑排序结果，若图存在环则返回空列表
     */
    public List<Integer> kahnSort() {
        // 计算每个节点的入度
        int[] inDegree = new int[numNodes];
        for (int u = 0; u < numNodes; u++) {
            for (int v : adjacencyList.get(u)) {
                inDegree[v]++;
            }
        }

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

        List<Integer> result = new ArrayList<>();

        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);

            // 移除节点u后，其所有邻接节点的入度减1
            for (int v : adjacencyList.get(u)) {
                inDegree[v]--;
                // 若邻接节点入度变为0，说明其所有前置依赖已满足
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        // 若结果节点数小于总节点数，说明图中存在环
        if (result.size() != numNodes) {
            System.out.println("图中存在环，无法进行拓扑排序！");
            return new ArrayList<>();
        }

        return result;
    }

    /**
     * DFS后序遍历实现拓扑排序
     * 核心思想：节点在其所有邻接节点处理完成后才加入结果
     *
     * @return 拓扑排序结果，若图存在环则返回空列表
     */
    public List<Integer> dfsSort() {
        // 0=未访问, 1=访问中(当前递归栈中), 2=已完成
        int[] state = new int[numNodes];
        // 使用Deque作为栈，将完成的节点压入栈中
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < numNodes; i++) {
            if (state[i] == 0) {
                if (!dfsHelper(i, state, stack)) {
                    System.out.println("图中存在环，无法进行拓扑排序！");
                    return new ArrayList<>();
                }
            }
        }

        // 从栈中弹出即为拓扑序（后序遍历的逆序）
        List<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }

    /**
     * DFS辅助方法
     *
     * @param u     当前节点
     * @param state 节点访问状态数组
     * @param stack 完成后序存储栈
     * @return 是否无环
     */
    private boolean dfsHelper(int u, int[] state, Deque<Integer> stack) {
        state[u] = 1; // 标记为访问中

        for (int v : adjacencyList.get(u)) {
            if (state[v] == 1) {
                // 遇到访问中的节点，说明存在环
                return false;
            }
            if (state[v] == 0) {
                if (!dfsHelper(v, state, stack)) {
                    return false;
                }
            }
        }

        state[u] = 2; // 标记为已完成
        stack.push(u); // 当前节点及其所有后代都已处理完毕
        return true;
    }

    /**
     * 获取所有可能的拓扑排序方案数量
     * 使用动态规划 + 状态压缩（适用于n <= 20的情况）
     *
     * @return 拓扑排序方案总数
     */
    public long countTopologicalSorts() {
        if (numNodes > 20) {
            throw new IllegalArgumentException("节点数过多，无法使用状态压缩DP");
        }

        // 预处理：计算每个节点的入度对应的二进制掩码
        int[] inMask = new int[numNodes];
        for (int u = 0; u < numNodes; u++) {
            for (int v : adjacencyList.get(u)) {
                inMask[v] |= (1 << u);
            }
        }

        // dp[mask] 表示已选择mask中节点的方案数
        long[] dp = new long[1 << numNodes];
        dp[0] = 1;

        for (int mask = 0; mask < (1 << numNodes); mask++) {
            if (dp[mask] == 0) continue;
            for (int u = 0; u < numNodes; u++) {
                // 若u已在mask中，跳过
                if ((mask & (1 << u)) != 0) continue;
                // 若u的所有前置依赖都已包含在mask中
                if ((inMask[u] & ~mask) == 0) {
                    dp[mask | (1 << u)] += dp[mask];
                }
            }
        }

        return dp[(1 << numNodes) - 1];
    }

    /**
     * 课程表问题：判断是否能完成所有课程
     * LeetCode 207 经典题型
     *
     * @param numCourses    课程总数
     * @param prerequisites 前置依赖数组 [a,b] 表示要学a必须先学b
     * @return 是否能完成所有课程
     */
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        TopologicalSort ts = new TopologicalSort(numCourses);
        for (int[] pre : prerequisites) {
            ts.addEdge(pre[1], pre[0]); // b -> a
        }
        return !ts.kahnSort().isEmpty();
    }

    /**
     * 课程表II：返回一个可行的学习顺序
     * LeetCode 210 经典题型
     *
     * @param numCourses    课程总数
     * @param prerequisites 前置依赖数组
     * @return 可行的学习顺序，若无法完成则返回空数组
     */
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        TopologicalSort ts = new TopologicalSort(numCourses);
        for (int[] pre : prerequisites) {
            ts.addEdge(pre[1], pre[0]);
        }
        List<Integer> order = ts.kahnSort();
        if (order.isEmpty()) return new int[0];
        return order.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 主方法：演示拓扑排序的各项功能
     */
    public static void main(String[] args) {
        // 示例：课程依赖关系
        // 0: 程序设计基础, 1: 数据结构, 2: 算法, 3: 操作系统, 4: 计算机网络
        // 依赖: 0->1, 0->3, 1->2, 3->4, 1->4
        TopologicalSort ts = new TopologicalSort(5);
        ts.addEdge(0, 1); // 程序设计基础 -> 数据结构
        ts.addEdge(0, 3); // 程序设计基础 -> 操作系统
        ts.addEdge(1, 2); // 数据结构 -> 算法
        ts.addEdge(3, 4); // 操作系统 -> 计算机网络
        ts.addEdge(1, 4); // 数据结构 -> 计算机网络

        System.out.println("=== Kahn算法拓扑排序 ===");
        List<Integer> kahnResult = ts.kahnSort();
        System.out.println("结果: " + kahnResult);

        System.out.println("\n=== DFS后序遍历拓扑排序 ===");
        TopologicalSort ts2 = new TopologicalSort(5);
        ts2.addEdge(0, 1);
        ts2.addEdge(0, 3);
        ts2.addEdge(1, 2);
        ts2.addEdge(3, 4);
        ts2.addEdge(1, 4);
        List<Integer> dfsResult = ts2.dfsSort();
        System.out.println("结果: " + dfsResult);

        // 环检测示例
        System.out.println("\n=== 环检测测试 ===");
        TopologicalSort cyclic = new TopologicalSort(3);
        cyclic.addEdge(0, 1);
        cyclic.addEdge(1, 2);
        cyclic.addEdge(2, 0); // 形成环 0->1->2->0
        List<Integer> cyclicResult = cyclic.kahnSort();
        System.out.println("有环图排序结果(应为空): " + cyclicResult);

        // 课程表问题
        System.out.println("\n=== 课程表问题 ===");
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        System.out.println("canFinish: " + canFinish(numCourses, prerequisites));
        System.out.println("findOrder: " + Arrays.toString(findOrder(numCourses, prerequisites)));

        // 拓扑排序方案数
        System.out.println("\n=== 拓扑排序方案数 ===");
        TopologicalSort ts3 = new TopologicalSort(4);
        ts3.addEdge(0, 1);
        ts3.addEdge(0, 2);
        ts3.addEdge(1, 3);
        ts3.addEdge(2, 3);
        System.out.println("方案数: " + ts3.countTopologicalSorts());
    }
}

复杂度分析

两种算法的核心差异在于处理顺序：Kahn算法”从入度为0的节点向外扩散”，类似BFS的层层推进；DFS后序法则”从叶子节点向内收缩”，依赖递归栈的后进先出特性。Kahn算法实现更直观，且易于扩展到”字典序最小拓扑序”（用优先队列替换普通队列）；DFS后序法代码更紧凑，且天然产生”逆拓扑序”。

应用场景

拓扑排序在实际工程中无处不在：

• 编译系统：make、Maven、Gradle 等工具通过拓扑排序确定编译顺序，确保依赖库先于使用它的模块编译
• 任务调度：操作系统和分布式调度器将任务依赖建模为DAG，拓扑排序生成可并行执行的任务批次
• 数据库迁移：Flyway、Liquibase等数据库迁移工具按依赖关系排序执行迁移脚本
• Excel公式计算：电子表格的单元格引用构成依赖图，拓扑排序确定计算顺序避免循环引用
• 数据流处理：Apache Flink、Spark等流处理引擎用拓扑排序规划算子执行顺序

拓扑排序不仅是算法竞赛中的经典题型，更是连接图论理论与工程实践的重要桥梁。它将抽象的依赖关系转化为具体的执行序列，是”把事情按正确顺序做完”这一朴素需求的数学表达。