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

❝

这是一道 「中等难度」 的题
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 。这是不可能的。

提示：

中的所有课程对互不相同

DFS（图的深度优先搜索）

上一题【算法题解】56. 课程表（图的广度优先搜索）使用了图的广度优先搜索算法，其实这道题同样可以使用 「图的深度优先搜索」 算法来实现。

同样的，我们将所有课程的依赖关系画出来，就会得到一个或者多个图。然后继续分析会发现，只要生成的图中没有环也就是没有循环依赖，就一定可以修完所有课程。所以可以将题意转换为求图中是否有环。

一个特别需要注意的地方，如下图所示：图1 绿色箭头标注的是可以修完全部课程的，图2 红色箭头才是真的存在循环依赖。

分析上面的两个图会发现，因为本题得出的图是单向图，所以只有DFS一路向下且没有回退的情况下，如果再次遇到访问过的节点，就表示有环。

如果回退后，再遇到访问过的节点就不算。如下所示，在访问完课程3 之后本次 DFS 遇到边界需要回退到课程2。

然后再访问到课程4，继而再一次访问到课程3，但这时因为不是在一次 DFS 相遇，所以不算有环。

实现要点：使用一个数组记录访问过的节点（课程），默认所有节点都是未访问过的，并标记为0。初次访问后标记为1，发生回退标记为2。如果再次访问到该节点，如果标记是2，说明是上一轮已经访问过了，认为没有环并可以直接递归回退本次 DFS。如果标记是1，说明是在本次 DFS 就相遇了，认为有环。

Java 代码实现

class Solution {
    private int[] visited;
    private boolean hasCycle = false;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        
        visited = new int[numCourses];

        // 出边数组
        List<Integer>[] toList = new List[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);
        }

        

        for(int i = 0; i < numCourses; i++){
            // 从任意没访问过的点开始都可以
            // 如果已经判断出有环了，后面的就不用管了
            if(visited[i] == 0 && !hasCycle){
                dfs(i, toList);
            }
        }

        return !hasCycle;

    }

    private void dfs(int course, List<Integer>[] toList){
        if(hasCycle){
            return;
        }

        if(visited[course] == 1){
            hasCycle = true;
            return;
        }

        if(visited[course] == 2){
            return;
        }

        visited[course] = 1;

        List<Integer> toCources = toList[course];
        if(toCources != null){
            for(int to : toCources){
                dfs(to, toList);
            }
        }

        visited[course] = 2;

    }

}

Go 代码实现

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

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

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

        toList[y] = append(toList[y], x)

    }

    visited := make([]int, numCourses)
    hasCycle := false

    var dfs func(i int)

    dfs = func(i int) {
        if hasCycle {
            return
        }

        if visited[i] == 1 {
            hasCycle = true
            return
        }

        if visited[i] == 2 {
            return
        }

        visited[i] = 1

        for _, to := range toList[i] {
            dfs(to)
        }

        visited[i] = 2

    }

    for i := 0; i < numCourses; i++ {
        if !hasCycle && visited[i] == 0 {
            dfs(i)
        }
    }

    return !hasCycle

}