本文主要是介绍【BFS拓扑排序】207. 课程表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
207. 课程表
解题思路
-
首先构建了一个 inDegree 哈希表，用于存储每门课程的入度，即有多少课程依赖当前课程。
-
构建了一个 adj 哈希表，用于存储每门课程所依赖的其他课程。这个结构可以理解为一个邻接表，对于每门课程，存储了其所有的前置课程。
-
根据给定的课程依赖关系数组 prerequisites，更新了每门课程的入度和依赖关系。
-
初始化一个队列 q，将所有入度为 0 的课程加入队列。这些课程是没有任何先修课程的课程，可以直接学习。
-
开始一个循环，每次从队列中取出一门课程，表示这门课程被选择学习。然后遍历其邻接表中的课程，将这些课程的入度减 1，并将入度减为 0 的课程加入队列，表示这些课程可以被学习了。
-
最后，遍历所有课程的入度，如果存在入度不为 0 的课程，说明存在环路，直接返回 false，表示无法完成所有课程的学习；否则返回 true，表示能够完成所有课程的学习。
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 先让入度为0 的课入队// 然后逐个出队 出队的课代表被选择，然后减小相关课程的入度// 如果相关课的入度为0 安排出队// 课程号和对应的入度Map<Integer,Integer> inDegree = new HashMap<>();// 将所有的课程先放入for(int i = 0; i < numCourses; i++){inDegree.put(i,0);}// 依赖关系 计算每一门课程所依赖的前面的课程// cur 依赖pre cur1依赖 pre 那么 pre ,(cur,cur1)Map<Integer,List<Integer>> adj = new HashMap<>();// 初始化入度和依赖的关系for(int[] relate: prerequisites){// 想要学cur 必须先完成pre 也就是cur 依赖pre pre指向cur 作为cur的一个入度int cur = relate[0];int pre = relate[1];// 更新入度inDegree.put(cur,inDegree.get(cur) + 1);// 入度 + 1if(!adj.containsKey(pre)){// 如果不存在依赖关系 先初始化adj.put(pre,new ArrayList<>());}adj.get(pre).add(cur);}Queue<Integer> q = new LinkedList<>();// 将所有入度为0 的全部入队for(int key:inDegree.keySet()){if(inDegree.get(key) == 0){q.offer(key);}}// 取出一个节点 对应学习这门课程// 遍历当前邻接表 更新其入度 更新之后 查看入度 如果为0 加入到队列while(!q.isEmpty()){int cur = q.poll();// 取出当前课程// 查看当前课程是否存在邻接表if(!adj.containsKey(cur)){continue;}List<Integer> successorList = adj.get(cur);// 取出它的邻接表// 遍历所有的需要依赖当前课程cur 的所有课程for(int k: successorList){// 依赖cur的课程 入度减小1inDegree.put(k,inDegree.get(k) - 1);// 入度减小1// 当依赖cur的课程 入度减小为1的时候 直接入队if(inDegree.get(k) == 0){q.offer(k);}}}// 遍历队列 如果还有课程的入度不为0 说明存在环路 直接falsefor(int key:inDegree.keySet()){if(inDegree.get(key) != 0){return false;}}return true;}
}这篇关于【BFS拓扑排序】207. 课程表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
