拓扑排序

210. 课程表 II

1. dfs实现

实际上就是在环检测算法的基础上，加入了一个后续遍历，并且对后续遍历的结果做了一个翻转，通过这种方式就可以保证一门课程的所有前置课程一定先于该课程被修读。

public class FindOrderByDFS_210 {
    // 访问控制数组，避免重复访问
    private boolean[] visited;
    // 记录当前路径上的节点访问情况，需要回溯，用于环检测
    private boolean[] onPath;
    // 用于记录环检测结果
    private boolean hasCycle;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];

        // 初始化邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }

        // 获取后续遍历结果
        List<Integer> postOrder = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i]) {
                dfs(graph, i, postOrder);
            }
        }
        // 翻转
        Collections.reverse(postOrder);
        int[] result = new int[0];
        // 根据环检测情况返回结果
        if (!hasCycle) {
            result = postOrder.stream().mapToInt(Integer::intValue).toArray();
        }
        return result;
    }

    private void dfs(List<List<Integer>> graph, int node, List<Integer> postOrder) {
        // 如果同意路径上出现重复节点，说明存在环，记录结果并返回
        if (onPath[node]) {
            hasCycle = true;
            return;
        }
        // 避免重复访问节点
        if (visited[node] || hasCycle) {
            return;
        }
        // 更新访问信息
        visited[node] = true;
        onPath[node] = true;
        // 遍历dfs
        for (Integer nextNode : graph.get(node)) {
            dfs(graph, nextNode, postOrder);
            // 剪枝
            if (hasCycle) {
                return;
            }
        }
        postOrder.add(node);
        onPath[node] = false;
    }
}

2. bfs实现

总的思路就是利用队列来保存下一轮要访问的节点，用入度数组来控制每一轮哪些节点应该入队——当入度为零，即当前节点的所有先修课都修读完毕之后，才可以修读这门课，这个访问的顺序就已经是一个拓扑排序的结果了，只需要按顺序把这些访问节点记录起来即可。

public class FindOrderByBFS_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[] prerequisite : prerequisites) {
            int from = prerequisite[1];
            int to = prerequisite[0];

            graph.get(from).add(to);
            inDegree[to]++;
        }

        // 将第一轮可以访问的节点入队
        Queue<Integer> que = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                que.offer(i);
            }
        }

        // count记录当前访问的节点数
        int count = 0;
        // 记录节点访问顺序
        int[] order = new int[numCourses];
        while (!que.isEmpty()) {
            int course = que.poll();
            order[count] = course;
            count++;
            // 遍历当前节点的子节点，将子节点的入度减一，若子节点入度为零，将其入队，下一轮即可访问
            for (Integer nextCourse : graph.get(course)) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] == 0) {
                    que.add(nextCourse);
                }
            }
        }

        // 若遍历节点数等于课程总数，说明无环，可以正常返回结果，否则返回空数组
        if (count == numCourses) {
            return order;
        } else {
            return new int[0];
        }
    }
}