207. 课程表（高频题）

207. 课程表

• 解题思路
• 代码

解题思路

这种有先决顺序的工程安排问题一般就是_拓扑排序_，这道题是拓扑排序的裸题。

拓扑排序其实一般就利用Map把拓扑图构建出来，然后用BFS去遍历拓扑图就好了。

则本题的大概思路为：

1. 统计每个课被指向次数，初始被指向次数为0的肯定是安全的（不在环上）。

2. 每被安全课程指向一次，被指次数减一，

3. 如果被指次数减到0，说明该课程全部指向都来自安全课程，则它也是安全的。

4. 依此进行队列循环。

详细解题思路见这篇文章

代码

class Solution {
        // 节点的入度: 使用数组保存每个节点的入度,
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1.课号和对应的入度
        Map<Integer, Integer> inDegree = new HashMap<>();
        // 将所有的课程先放入
        for (int i = 0; i < numCourses; i++) {
            inDegree.put(i, 0);
        }
        // 2.依赖关系, 依赖当前课程的后序课程
        Map<Integer, List<Integer>> adj = new HashMap<>();


        // 初始化入度和依赖关系
        for (int[] relate : prerequisites) {
            // (3,0), 想学3号课程要先完成0号课程, 更新3号课程的入度和0号课程的依赖(邻接表)
            int cur = relate[1];
            int next = relate[0];
            // 1.更新入度
            inDegree.put(next, inDegree.get(next) + 1);
            // 2.当前节点的邻接表（即3依赖于0）
            if (!adj.containsKey(cur)) {
                adj.put(cur, new ArrayList<>());
            }
            adj.get(cur).add(next);
        }

        // 3.BFS, 将入度为0的课程放入队列, 队列中的课程就是没有先修, 可以学的课程
Queue<Integer> q=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(inDegger.get(i)==0){
                q.add(i);
            }
        }

        while(!q.isEmpty()){
           int size=q.size();
           for(int i=0;i<q.size();i++){
               int temp=q.poll();
               if(adj.containsKey(temp)){
                ArrayList<Integer> t=adj.get(temp);
                for(int j=0;j<t.size();j++){
                    inDegger.put(t.get(j),inDegger.get(t.get(j))-1);
                    if(inDegger.get(t.get(j))==0){
                        q.add(t.get(j));
                    }
                }
               }
           } 
        }

        for(int i=0;i<numCourses;i++){
            if(inDegger.get(i)!=0){
                return false;
            }
        }
        return true;
    }
}