环检测算法

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
207. Course Schedule	207. 课程表

前置知识

阅读本文前，你需要先学习：

一句话总结

用 DFS 的 onPath 数组或 BFS 的入度数组，可以判断有向图中是否存在环。

有向图的环检测是图论中一个非常基本且实用的算法。比如我们写代码 import 包的时候，如果存在循环依赖，编译器会报错，编译器内部就用到了类似的环检测算法。再比如任务调度系统中，如果任务之间的依赖关系成环了，那这些任务就永远无法被执行。

本文就结合具体的算法题，分别用 DFS 和 BFS 两种思路来实现有向图的环检测算法。

相对而言 BFS 解法从代码实现上看更简洁一些，但 DFS 解法有助于你进一步理解递归遍历数据结构的奥义，所以本文中我先讲 DFS 遍历的思路，再讲 BFS 遍历的思路。

环检测算法（DFS 版本）

先来看看力扣第 207 题「课程表」：

207. 课程表|力扣|LeetCode

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

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a_i, b_i] ，表示如果要学习课程 a_i 则必须先学习课程 b_i。

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

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

示例 1：

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

示例 2：

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

提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
prerequisites[i] 中的所有课程对 互不相同

题目来源：力扣 207. 课程表。

// 函数签名如下
boolean canFinish(int numCourses, int[][] prerequisites);

题目应该不难理解，什么时候无法修完所有课程？当存在循环依赖的时候。

看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。

具体来说，我们首先可以把课程看成「有向图」中的节点，节点编号分别是 0, 1, ..., numCourses-1，把课程之间的依赖关系看做节点之间的有向边。

比如说必须修完课程 1 才能去修课程 3，那么就有一条有向边从节点 1 指向 3。

所以我们可以根据题目输入的 prerequisites 数组生成一幅类似这样的图：

如果发现这幅有向图中存在环，那就说明课程之间存在循环依赖，肯定没办法全部上完；反之，如果没有环，那么肯定能上完全部课程。

好，那么想解决这个问题，首先我们要把题目的输入转化成一幅有向图，然后再判断图中是否存在环。

前文图结构的存储写过图的两种存储形式，邻接矩阵和邻接表。这里我就用邻接表形式存储图吧，写一个建图函数：

List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 图中共有 numCourses 个节点
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        // 添加一条从 from 指向 to 的有向边
        // 边的方向是「被依赖」关系，即修完课程 from 才能修课程 to
        graph[from].add(to);
    }
    return graph;
}

图建出来了，怎么判断图中有没有环呢？

也很简单，就是考你如何遍历图中的所有路径嘛，如果我能遍历所有路径，那么路径是否成环肯定能算出来。

图的 DFS/BFS 遍历基础写了如何用 DFS 算法遍历图的所有路径，如果忘记了请去复习，下面要用到。

我这里先直接套用遍历所有路径的 DFS 代码模板，用一个 hasCycle 变量记录是否存在环，当重复遍历到 onPath 中的节点时，就说明遇到了环，设置 hasCycle = true。

基于这个思路，先看第一版代码（会超时）：

class Solution {
    // 记录递归堆栈中的节点
    boolean[] onPath;
    // 记录图中是否有环
    boolean hasCycle = false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        
        onPath = new boolean[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            // 遍历图中的所有节点
            traverse(graph, i);
        }
        // 只要没有循环依赖可以完成所有课程
        return !hasCycle;
    }

    // 图遍历函数，遍历所有路径
    void traverse(List<Integer>[] graph, int s) {
        if (hasCycle) {
            // 如果已经找到了环，也不用再遍历了
            return;
        }

        if (onPath[s]) {
            // s 已经在递归路径上，说明成环了
            hasCycle = true; 
            return;
        }
        
        // 前序代码位置
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        // 后序代码位置
        onPath[s] = false;
    }

    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        // 代码见前文
    }
}

注意图中并不是所有节点都相连，所以要用一个 for 循环将所有节点都作为起点调用一次 DFS 搜索算法。

其实这个解法已经是正确的了，因为遍历了所有路径，一定可以判定是否成环。但是这个解法无法通过所有测试用例，会超时。原因肯定也能猜出来，有冗余计算呗。

哪里有冗余计算呢？我举个例子你就明白了。

假设现在你以节点 2 为起点遍历所有可达的路径，最终发现没有环。

假设另一个节点 5 有一条指向 2 的边，你再以 5 为起点遍历所有可达的路径时，肯定还会走到 2，那么请问，此时你是否还需要继续遍历 2 的所有可达路径呢？

答案是不需要了，因为第一次你没找到环，那么这次也不可能找到环。想明白这里面的冗余计算没有？你如果觉得有反例，可以自己画一下，实际上是没有反例的。

那么对症下药就行了：如果我们发现一个节点之前被遍历过，就可以直接跳过，不用再重复遍历了。

优化后的代码如下：

class Solution {
    // 记录一次递归堆栈中的节点
    boolean[] onPath;
    // 记录节点是否被遍历过
    boolean[] visited;
    // 记录图中是否有环
    boolean hasCycle = false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        
        onPath = new boolean[numCourses];
        visited = new boolean[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            // 遍历图中的所有节点
            traverse(graph, i);
        }
        // 只要没有循环依赖可以完成所有课程
        return !hasCycle;
    }

    // 图遍历函数，遍历所有路径
    void traverse(List<Integer>[] graph, int s) {
        if (hasCycle) {
            // 如果已经找到了环，也不用再遍历了
            return;
        }

        if (onPath[s]) {
            // s 已经在递归路径上，说明成环了
            hasCycle = true; 
            return;
        }
        
        if (visited[s]) {
            // 不用再重复遍历已遍历过的节点
            return;
        }

        // 前序代码位置
        visited[s] = true;
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        // 后序代码位置
        onPath[s] = false;
    }


    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        // 代码见前文
    }
}

visited 为 true 的节点为绿色，onPath 为 true 的节点为橙色。

你可以打开可视化面板，多次点击 if (onPath[s]) 这部分代码，即可查看 DFS 遍历图的过程。

算法可视化

这道题就解决了，核心就是判断一幅有向图中是否存在环。

不过如果出题人继续提问，让你不仅要判断是否存在环，还要返回这个环具体有哪些节点，怎么办？

你可能说，onPath 里面为 true 的索引，不就是组成环的节点编号吗？

不是的，假设从节点 0 开始遍历，下图中绿色的节点是递归的路径，它们在 onPath 中的值都是 true，但显然成环的节点只是其中的一部分：

这个问题大家可以先思考一下，办法肯定有很多啦，我只给出一个常用的解法。

点击查看答案

最简单直接的解法是，在 boolean[] onPath 数组的基础上，我们再使用一个 Stack<Integer> path 栈，把遍历过程中经过的节点顺序也保存下来。

比如按照上图绿色的遍历顺序，path 从栈底到栈顶的元素就是 [0,4,5,9,8,7,6]。此时又一次遇到了节点 5，那么就可以知道 [5,9,8,7,6] 这部分是环了。

环检测算法（BFS 版本）

上面讲了用 DFS 算法利用 onPath 数组判断是否存在环，接下来看看如何用 BFS 算法来解决这个问题。

BFS 算法借助 indegree 数组记录每个节点的「入度」，可以实现环检测算法。不熟悉 BFS 算法的读者可阅读前文图结构的 BFS 遍历。

直接看 BFS 算法的解法代码：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 建图，有向边代表「被依赖」关系
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        // 构建入度数组
        int[] indegree = new int[numCourses];
        for (int[] edge : prerequisites) {
            int from = edge[1], to = edge[0];
            // 节点 to 的入度加一
            indegree[to]++;
        }

        // 根据入度初始化队列中的节点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                // 节点 i 没有入度，即没有依赖的节点
                // 可以作为拓扑排序的起点，加入队列
                q.offer(i); 
            }
        }

        // 记录遍历的节点个数
        int count = 0;
        // 开始执行 BFS 循环
        while (!q.isEmpty()) {
            // 弹出节点 cur，并将它指向的节点的入度减一
            int cur = q.poll();
            count++;
            for (int next : graph[cur]) { 
                indegree[next]--;
                if (indegree[next] == 0) {
                    // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                    q.offer(next);
                }
            }
        }

        // 如果所有节点都被遍历过，说明不成环
        return count == numCourses;
    }

    // 建图函数
    List<Integer>[] buildGraph(int n, int[][] edges) {
        // 见前文
    }
}