【算法题解】56. 课程表（图的广度优先搜索）

❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/course-schedule/

❞

题目

你这个学期必须选修门课程，记为到。

在选修某些课程之前需要一些先修课程。先修课程按数组给出，其中，表示如果要学习课程则 「必须」 先学习课程。

例如，先修课程对表示：想要学习课程，你需要先完成课程。

请你判断是否可能完成所有课程的学习？如果可以，返回；否则，返回。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]] 
输出：true 
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 
输出：false 
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；
并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

中的所有课程对互不相同

BFS（图的广度优先搜索）

我们将所有课程的依赖关系画出来，就会得到一个或者多个图。如图所示，开始时只有课程1 和课程5 可以直接选修，因为它俩没有依赖任何其他课程。

当课程1 和课程5 修完之后，课程2、课程3 以及课程6 就都可以选修了。

同样的，当课程2 和课程3 全部修完之后，课程4 的所有依赖课程全部修完，这个时候课程4 也就可以选修了。

根据上述选课的步骤，可以很明显的看出：

选修的过程是沿着图的层级结构，一层一层的去选的，所以我们可以考虑使用图的「广度优先搜索」来完成选课。
只有当前课程依赖的所有课程都已经修完，当前课程才能选修。对应到图中，就是只有当入度为0时才能选修。

入度的概念：入度就是进入一个节点的边的数量。

如上图中课程4 开始的入度是2，因为有2个依赖，对应到图中就是有2条进入的边。当课程2 修完后，就只依赖课程3 了，这个时候课程4 的入度是1，还不能选修。当课程3 也修完后，课程4 的入度变为0，可以选修。

总体实现思路为：

构建图并计算每个节点的初始入度。
先找到初始入度为0的所有节点（课程），然后分别以这些节点开始进行图的广度优先搜索。
搜索完一个节点，就将其下一级的所有的节点的入度减1，如果减1后入度为0，就可以放入队列进行搜索。
如果所有的节点全部搜索完毕，或者说搜索完毕的节点数等于给定的课程数，就表示可以选修完所有的课程。

Java 代码实现

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 出边数组
        List<Integer>[] toList = new List[numCourses];

        // 入度
        int[] inDeg = new int[numCourses];

        // 构建图
        for(int[] requisite : prerequisites){
            // 课程x 依赖 课程y
            int x = requisite[0];
            int y = requisite[1];

            if(toList[y] == null){
                toList[y] = new ArrayList<Integer>();
            }
            toList[y].add(x);
            inDeg[x]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        
        for(int i = 0; i < numCourses; i++){
            // 入度为0， 可以直接修
            if(inDeg[i] == 0){
                queue.offer(i);
            }
        }

        int completed = 0;
        while(!queue.isEmpty()){
            int course = queue.poll();
            completed++;
            List<Integer> toCourses = toList[course];
            if(toCourses != null){
                for(int to : toCourses){
                    inDeg[to]--;
                    if(inDeg[to] == 0){
                        queue.offer(to);
                    }
                }
            }

        }

       return completed == numCourses;

    }

}

Go 代码实现

func canFinish(numCourses int, prerequisites [][]int) bool {

    toList := make([][]int, numCourses)

    inDeg := make([]int, numCourses)

    for i := 0; i < len(prerequisites); i++ {
        x := prerequisites[i][0]
        y := prerequisites[i][1]

        toList[y] = append(toList[y], x)
        inDeg[x]++
    }


    queue := []int{}
    for i := 0; i < numCourses; i++{
        if inDeg[i] == 0 {
            queue = append(queue, i)
        }
    }

    completed := 0

    for len(queue) > 0 {
        course := queue[0]
        queue = queue[1:]

        completed++
        
        for _, to := range toList[course] {
            inDeg[to]--
            if inDeg[to] == 0 {
                queue = append(queue, to)
            }
        }

    }
    return completed == numCourses

}