LeetCode_拓扑排序_BFS_中等_210.课程表 II-蒲公英云

LeetCode_拓扑排序_BFS_中等_210.课程表 II

1.题目

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3]。另一个正确的排序是 [0,2,1,3] 。

示例 3：
输入：numCourses = 1, prerequisites = []
输出：[0]

提示：
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/course-schedule-ii

2.思路

（1）拓扑排序_BFS
本题与LeetCode_环检测_DFS_中等_207.课程表这题类似，只不过本题需要返回你为了学完所有课程所安排的学习顺序。

相关题目：
LeetCode_环检测_DFS_中等_207.课程表
LeetCode_贪心算法_困难_630.课程表 III

3.代码实现（Java）

//思路1————拓扑排序_BFS
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //通过题目信息创建有向图，使用邻接表存储
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        //计算图中每个节点的入度，inDegree[i] = j 表示节点 i 的入度为 j
        int[] inDegree = new int[numCourses];
        for (int[] edge : prerequisites) {
            //修完课程 from 才能修课程 to，即在图中节点 from 指向节点 to
            int to = edge[0];
            inDegree[to]++;
        }
        //将入度为 0 的节点加入到队列中
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        //记录拓扑排序的结果(即课程安排的学习顺序)
        int[] res = new int[numCourses];
        //记录遍历节点的顺序
        int cnt = 0;
        //通过 BFS 算法完成拓扑排序
        while (!queue.isEmpty()) {
            //取出队首节点
            int cur = queue.poll();
            //取出的节点顺序即为拓扑排序的结果
            res[cnt++] = cur;
            //遍历当前节点所指向的所有节点
            for (int next : graph[cur]) {
                //去掉 cur 指向 next 的边，故 next 的入度减 1
                inDegree[next]--;
                //将入度为 0 的节点再次加入到队列中
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return cnt == numCourses ? res : new int[]{
    };
    }
    /*
        利用题目所给信息构建有向图，通过邻接表存储
        其中 numCourses 表示节点个数，prerequisites 存储节点之间的关系 
    */
    public List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        //图中共有 numCourses 个节点
        List<Integer>[] graph = new ArrayList[numCourses];
        //创建 numCourses 个节点
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        //创建节点之间的关系(即有向边)
        for (int[] edge : prerequisites) {
            int from = edge[1];
            int to = edge[0];
            //修完课程 from 才能修课程 to，即在图中添加一条从 from 指向 to 的有向边
            graph[from].add(to);
        }
        return graph;
    }
}