拓扑排序：课程表问题

拓扑排序基础（Kahn 算法 / BFS）

将所有入度为 0 的节点入队，每次取出并移除其边，若有新的入度为 0 的节点则入队：

// 通用拓扑排序模板
public int[] topoSort(int n, int[][] edges) {
    int[] inDegree = new int[n];
    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]);
        inDegree[e[1]]++;
    }
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (inDegree[i] == 0) queue.offer(i);
    int[] order = new int[n];
    int idx = 0;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order[idx++] = node;
        for (int next : graph.get(node)) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }
    return idx == n ? order : new int[0];  // 有环则返回空数组
}

课程表（LeetCode 207）

有向图检测环（等价于判断是否存在拓扑序）：

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    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]);
        inDegree[p[0]]++;
    }
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) queue.offer(i);
    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int next : graph.get(course))
            if (--inDegree[next] == 0) queue.offer(next);
    }
    return count == numCourses;
}

课程表 II（LeetCode 210）

返回具体拓扑顺序（若有环返回空数组）：

public int[] findOrder(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    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]);
        inDegree[p[0]]++;
    }
    Queue<Integer> queue = new ArrayDeque<>();
    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];
}

DFS 版拓扑排序（三色标记检测环）

状态：0=未访问，1=访问中（灰），2=已完成（黑）：

public boolean canFinish(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]);
    int[] color = new int[numCourses]; // 0=白, 1=灰, 2=黑
    for (int i = 0; i < numCourses; i++)
        if (color[i] == 0 && hasCycle(graph, color, i)) return false;
    return true;
}
private boolean hasCycle(List<List<Integer>> graph, int[] color, int node) {
    color[node] = 1; // 标记为访问中
    for (int next : graph.get(node)) {
        if (color[next] == 1) return true;  // 发现灰色节点 → 有环
        if (color[next] == 0 && hasCycle(graph, color, next)) return true;
    }
    color[node] = 2;
    return false;
}

总结