拓扑排序

什么是拓扑排序？

拓扑排序是对**有向无环图（DAG）**的节点进行线性排序，使得对于每条有向边 u → v，u 在排序中出现在 v 之前。

应用场景：任务调度、课程选修顺序、编译器依赖分析、项目管理（PERT图）。

如果图中有环，则无法进行拓扑排序（先修课程出现循环依赖 → 无解）。

Kahn 算法（BFS 方法）

核心思想：不断选取入度为 0 的节点（无前置依赖），加入结果，同时更新邻居节点的入度。

List<Integer> topoSort(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[] e : edges) {
        graph.get(e[0]).add(e[1]);
        inDegree[e[1]]++;
    }
    // 将所有入度=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);
        }
    }
    // 如果结果长度 < n，说明图中有环
    return result.size() == n ? result : new ArrayList<>();
}

时间：O(V + E)，空间：O(V + E)。

DFS 拓扑排序（后序反转）

DFS 完成一个节点（其所有后继都处理完）时，将其加入栈；最后反转栈得到拓扑序。

int[] color;     // 0=白(未访问), 1=灰(访问中), 2=黑(完成)
Deque<Integer> stack;
boolean hasCycle;

void dfs(List<List<Integer>> graph, int node) {
    if (hasCycle) return;
    color[node] = 1;
    for (int neighbor : graph.get(node)) {
        if (color[neighbor] == 1) { hasCycle = true; return; }
        if (color[neighbor] == 0) dfs(graph, neighbor);
    }
    color[node] = 2;
    stack.push(node);  // 后序：所有后继处理完才入栈
}

List<Integer> topoSortDFS(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) graph.get(e[0]).add(e[1]);
    color = new int[n];
    stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) dfs(graph, i);
    }
    if (hasCycle) return new ArrayList<>();
    List<Integer> result = new ArrayList<>(stack);
    return result;
}

经典例题：课程表 II

给定 numCourses 门课程，prerequisites[i] = [a, b] 表示学 a 前必须先学 b，返回一种可行的上课顺序。

int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);  // b → a
        inDegree[pre[0]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }
    int[] order = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        order[idx++] = course;
        for (int next : graph.get(course)) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }
    return idx == numCourses ? order : new int[0];  // 有环则返回空数组
}

判断是否存在拓扑序（有无环）

boolean canFinish(int n, int[][] prerequisites) {
    // 同上，只是判断 result.size() == n
    return topoSort(n, prerequisites).size() == n;
}

拓扑排序的两种方法对比

时间复杂度：两者均为 O(V + E)