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

妖狐艹你老母 2023-10-06 22:37 145阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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\_环检测\_DFS\_中等\_207.课程表][LeetCode_DFS_207.]  
[LeetCode\_贪心算法\_困难\_630.课程表 III][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;
        }
    }

[LeetCode_DFS_207.]: https://blog.csdn.net/weixin_43004044/article/details/124522936
[LeetCode_630._ III]: https://blog.csdn.net/weixin_43004044/article/details/132800584