环检测算法及拓扑排序（修订版）
后台回复进群一起刷力扣 点击卡片可搜索关键词👇
207.课程表（Medium）
210.课程表 II（Medium）
写在开头：
本文是之前发的 拓扑排序，YYDS 的修订版，补充了大量内容。
首先，我说将后序遍历结果进行反转就是拓扑排序的结果，有的读者说他看到的很多解法直接使用后序遍历，并没有进行反转，本文新增了对此的解释。
另外，有读者说，用 BFS 算法通过计算入度去解决拓扑排序问题更简洁。这个看法我也认同，所以本文也添加了拓扑排序算法的 BFS 实现，供大家参考。
以下是正文：
图这种数据结构有一些比较特殊的算法，比如二分图判断，有环图无环图的判断，拓扑排序，以及最经典的最小生成树，单源最短路径问题，更难的就是类似网络流这样的问题。
不过以我的经验呢，像网络流这种问题，你又不是打竞赛的，没时间的话就没必要学了；像 最小生成树 和 最短路径问题，虽然从刷题的角度用到的不多，但它们属于经典算法，学有余力可以掌握一下；像 二分图判定、拓扑排序这一类，属于比较基本且有用的算法，应该比较熟练地掌握。
那么本文就结合具体的算法题，来说两个图论算法：有向图的环检测、拓扑排序算法。
这两个算法既可以用 DFS 思路解决，也可以用 BFS 思路解决，相对而言 BFS 解法从代码实现上看更简洁一些，但 DFS 解法有助于你进一步理解递归遍历数据结构的奥义。
所以本文中我先讲 DFS 遍历的思路，再讲 BFS 遍历的思路。
环检测算法（DFS 版本）
先来看看力扣第 207 题「课程表」：
函数签名如下：
boolean canFinish(int numCourses, int[][] prerequisites);
题目应该不难理解，什么时候无法修完所有课程？当存在循环依赖的时候。
其实这种场景在现实生活中也十分常见，比如我们写代码 import 包也是一个例子，必须合理设计代码目录结构，否则会出现循环依赖，编译器会报错，所以编译器实际上也使用了类似算法来判断你的代码是否能够成功编译。
看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。
具体来说，我们首先可以把课程看成「有向图」中的节点，节点编号分别是 0, 1, ..., numCourses-1，把课程之间的依赖关系看做节点之间的有向边。
比如说必须修完课程 1 才能去修课程 3，那么就有一条有向边从节点 1 指向 3。
所以我们可以根据题目输入的 prerequisites 数组生成一幅类似这样的图：
如果发现这幅有向图中存在环，那就说明课程之间存在循环依赖，肯定没办法全部上完；反之，如果没有环，那么肯定能上完全部课程。
好，那么想解决这个问题，首先我们要把题目的输入转化成一幅有向图，然后再判断图中是否存在环。
如何转换成图呢？我们前文 图论基础 写过图的两种存储形式，邻接矩阵和邻接表。
以我刷题的经验，常见的存储方式是使用邻接表，比如下面这种结构：
List<Integer>[] graph;
graph[s] 是一个列表，存储着节点 s 所指向的节点。
所以我们首先可以写一个建图函数：
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 算法遍历图的框架，无非就是从多叉树遍历框架扩展出来的，加了个 visited 数组罢了：
// 防止重复遍历同一个节点
boolean[] visited;
// 从节点 s 开始 DFS 遍历，将遍历过的节点标记为 true
void traverse(List<Integer>[] graph, int s) {
if (visited[s]) {
return;
}
/* 前序遍历代码位置 */
// 将当前节点标记为已遍历
visited[s] = true;
for (int t : graph[s]) {
traverse(graph, t);
}
/* 后序遍历代码位置 */
}
那么我们就可以直接套用这个遍历代码：
// 防止重复遍历同一个节点
boolean[] visited;
boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
visited = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
traverse(graph, i);
}
}
void traverse(List<Integer>[] graph, int s) {
// 代码见上文
}
注意图中并不是所有节点都相连，所以要用一个 for 循环将所有节点都作为起点调用一次 DFS 搜索算法。
这样，就能遍历这幅图中的所有节点了，你打印一下 visited 数组，应该全是 true。
现在可以思考如何判断这幅图中是否存在环。
我们前文 回溯算法核心套路详解 说过，你可以把递归函数看成一个在递归树上游走的指针，这里也是类似的：
你也可以把 traverse 看做在图中节点上游走的指针，只需要再添加一个布尔数组 onPath 记录当前 traverse 经过的路径：
boolean[] onPath;
boolean[] visited;
boolean hasCycle = false;
void traverse(List<Integer>[] graph, int s) {
if (onPath[s]) {
// 发现环！！！
hasCycle = true;
}
if (visited[s] || hasCycle) {
return;
}
// 将节点 s 标记为已遍历
visited[s] = true;
// 开始遍历节点 s
onPath[s] = true;
for (int t : graph[s]) {
traverse(graph, t);
}
// 节点 s 遍历完成
onPath[s] = false;
}
这里就有点回溯算法的味道了，在进入节点 s 的时候将 onPath[s] 标记为 true，离开时标记回 false，如果发现 onPath[s] 已经被标记，说明出现了环。
注意 visited 数组和 onPath 数组的区别，因为二叉树算是特殊的图，所以用遍历二叉树的过程来理解下这两个数组的区别：
上述 GIF 描述了递归遍历二叉树的过程，在 visited 中被标记为 true 的节点用灰色表示，在 onPath 中被标记为 true 的节点用绿色表示。
PS：类比贪吃蛇游戏，
visited记录蛇经过过的格子，而onPath仅仅记录蛇身。onPath用于判断是否成环，类比当贪吃蛇自己咬到自己（成环）的场景。
这样，就可以在遍历图的过程中顺便判断是否存在环了，完整代码如下：
// 记录一次递归堆栈中的节点
boolean[] onPath;
// 记录遍历过的节点，防止走回头路
boolean[] visited;
// 记录图中是否有环
boolean hasCycle = false;
boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
visited = new boolean[numCourses];
onPath = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
// 遍历图中的所有节点
traverse(graph, i);
}
// 只要没有循环依赖可以完成所有课程
return !hasCycle;
}
void traverse(List<Integer>[] graph, int s) {
if (onPath[s]) {
// 出现环
hasCycle = true;
}
if (visited[s] || hasCycle) {
// 如果已经找到了环，也不用再遍历了
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) {
// 代码见前文
}
这道题就解决了，核心就是判断一幅有向图中是否存在环。
不过如果出题人继续恶心你，让你不仅要判断是否存在环，还要返回这个环具体有哪些节点，怎么办？
你可能说，onPath 里面为 true 的索引，不就是组成环的节点编号吗？
不是的，假设下图中绿色的节点是递归的路径，它们在 onPath 中的值都是 true，但显然成环的节点只是其中的一部分：
这个问题留给大家思考，我会在公众号留言区置顶正确的答案。
那么接下来，我们来再讲一个经典的图算法：拓扑排序。
拓扑排序算法（DFS 版本）
看下力扣第 210 题「课程表 II」：
这道题就是上道题的进阶版，不是仅仅让你判断是否可以完成所有课程，而是进一步让你返回一个合理的上课顺序，保证开始修每个课程时，前置的课程都已经修完。
函数签名如下：
int[] findOrder(int numCourses, int[][] prerequisites);
这里我先说一下拓扑排序（Topological Sorting）这个名词，网上搜出来的定义很数学，这里干脆用百度百科的一幅图来让你直观地感受下：
直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的，比如上图所有箭头都是朝右的。
很显然，如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。
但是我们这道题和拓扑排序有什么关系呢？
其实也不难看出来，如果把课程抽象成节点，课程之间的依赖关系抽象成有向边，那么这幅图的拓扑排序结果就是上课顺序。
首先，我们先判断一下题目输入的课程依赖是否成环，成环的话是无法进行拓扑排序的，所以我们可以复用上一道题的主函数：
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (!canFinish(numCourses, prerequisites)) {
// 不可能完成所有课程
return new int[]{};
}
// ...
}
那么关键问题来了，如何进行拓扑排序？是不是又要秀什么高大上的技巧了？
其实特别简单，将后序遍历的结果进行反转，就是拓扑排序的结果。
PS：有的读者提到，他在网上看到的拓扑排序算法不用对后序遍历结果进行反转，这是为什么呢？
你确实可以看到这样的解法，原因是他建图的时候对边的定义和我不同。我建的图中箭头方向是「被依赖」关系，比如节点 1 指向 2，含义是节点 1 被节点 2 依赖，即做完 1 才能去做 2，
如果你反过来，把有向边定义为「依赖」关系，那么整幅图中边全部反转，就可以不对后序遍历结果反转。具体来说，就是把我的解法代码中 graph[from].add(to); 改成 graph[to].add(from); 就可以不反转了。
不过呢，现实中一般都是从初级任务指向进阶任务，所以像我这样把边定义为「被依赖」关系可能比较符合我们的认知习惯。
直接看解法代码吧，在上一题环检测的代码基础上添加了记录后序遍历结果的逻辑：
// 记录后序遍历结果
List<Integer> postorder = new ArrayList<>();
// 记录是否存在环
boolean hasCycle = false;
boolean[] visited, onPath;
// 主函数
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
visited = new boolean[numCourses];
onPath = new boolean[numCourses];
// 遍历图
for (int i = 0; i < numCourses; i++) {
traverse(graph, i);
}
// 有环图无法进行拓扑排序
if (hasCycle) {
return new int[]{};
}
// 逆后序遍历结果即为拓扑排序结果
Collections.reverse(postorder);
int[] res = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = postorder.get(i);
}
return res;
}
// 图遍历函数
void traverse(List<Integer>[] graph, int s) {
if (onPath[s]) {
// 发现环
hasCycle = true;
}
if (visited[s] || hasCycle) {
return;
}
// 前序遍历位置
onPath[s] = true;
visited[s] = true;
for (int t : graph[s]) {
traverse(graph, t);
}
// 后序遍历位置
postorder.add(s);
onPath[s] = false;
}
// 建图函数
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
// 代码见前文
}
代码虽然看起来多，但是逻辑应该是很清楚的，只要图中无环，那么我们就调用 traverse 函数对图进行 DFS 遍历，记录后序遍历结果，最后把后序遍历结果反转，作为最终的答案。
那么为什么后序遍历的反转结果就是拓扑排序呢？
我这里也避免数学证明，用一个直观地例子来解释，我们就说二叉树，这是我们说过很多次的二叉树遍历框架：
void traverse(TreeNode root) {
// 前序遍历代码位置
traverse(root.left)
// 中序遍历代码位置
traverse(root.right)
// 后序遍历代码位置
}
二叉树的后序遍历是什么时候？遍历完左右子树之后才会执行后序遍历位置的代码。换句话说，当左右子树的节点都被装到结果列表里面了，根节点才会被装进去。
后序遍历的这一特点很重要，之所以拓扑排序的基础是后序遍历，是因为一个任务必须等到它依赖的所有任务都完成之后才能开始开始执行。
你把二叉树理解成一幅有向图，边的方向是由父节点指向子节点，那么就是下图这样：
按照我们的定义，边的含义是「被依赖」关系，那么上图的拓扑排序应该首先是节点 1，然后是 2, 3，以此类推。
但显然标准的后序遍历结果不满足拓扑排序，而如果把后序遍历结果反转，就是拓扑排序结果了：
以上，我直观解释了一下为什么「拓扑排序的结果就是反转之后的后序遍历结果」，当然，我的解释并没有严格的数学证明，有兴趣的读者可以自己查一下。
环检测算法（BFS 版本）
刚才讲了用 DFS 算法利用 onPath 数组判断是否存在环；也讲了用 DFS 算法利用逆后序遍历进行拓扑排序。
其实 BFS 算法借助 indegree 数组记录每个节点的「入度」，也可以实现这两个算法。不熟悉 BFS 算法的读者可阅读前文 BFS 算法核心框架。
所谓「出度」和「入度」是「有向图」中的概念，很直观：如果一个节点x有a条边指向别的节点，同时被b条边所指，则称节点x的出度为a，入度为b。
先说环检测算法，直接看 BFS 的解法代码：
// 主函数
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 建图，有向边代表「被依赖」关系
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
// 构建入度数组
int[] indgree = new int[numCourses];
for (int[] edge : prerequisites) {
int from = edge[1], to = edge[0];
// 节点 to 的入度加一
indgree[to]++;
}
// 根据入度初始化队列中的节点
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indgree[i] == 0) {
// 节点 i 没有入度，即没有依赖的节点
// 可以作为拓扑排序的起点，加入队列
q.offer(i);
}
}
// 记录遍历的节点个数
int count = 0;
// 开始执行 BFS 循环
while (!q.isEmpty()) {
// 弹出节点 cur，并将它指向的节点的入度减一
int cur = q.poll();
count++;
for (int next : graph[cur]) {
indgree[next]--;
if (indgree[next] == 0) {
// 如果入度变为 0，说明 next 依赖的节点都已被遍历
q.offer(next);
}
}
}
// 如果所有节点都被遍历过，说明不成环
return count == numCourses;
}
// 建图函数
List<Integer>[] buildGraph(int n, int[][] edges) {
// 见前文
}
我先总结下这段 BFS 算法的思路：
1、构建邻接表，和之前一样，边的方向表示「被依赖」关系。
2、构建一个 indegree 数组记录每个节点的入度，即 indegree[i] 记录节点 i 的入度。
3、对 BFS 队列进行初始化，将入度为 0 的节点首先装入队列。
4、开始执行 BFS 循环，不断弹出队列中的节点，减少相邻节点的入度，并将入度变为 0 的节点加入队列。
5、如果最终所有节点都被遍历过（count 等于节点数），则说明不存在环，反之则说明存在环。
我画个图你就容易理解了，比如下面这幅图，节点中的数字代表该节点的入度：
队列进行初始化后，入度为 0 的节点首先被加入队列：
开始执行 BFS 循环，从队列中弹出一个节点，减少相邻节点的入度，同时将新产生的入度为 0 的节点加入队列：
继续从队列弹出节点，并减少相邻节点的入度，这一次没有新产生的入度为 0 的节点：
继续从队列弹出节点，并减少相邻节点的入度，同时将新产生的入度为 0 的节点加入队列：
继续弹出节点，直到队列为空：
这时候，所有节点都被遍历过一遍，也就说明图中不存在环。
反过来说，如果按照上述逻辑执行 BFS 算法，存在节点没有被遍历，则说明成环。
比如下面这种情况，队列中最初只有一个入度为 0 的节点：
当弹出这个节点并减小相邻节点的入度之后队列为空，但并没有产生新的入度为 0 的节点加入队列，所以 BFS 算法终止：
你看到了，如果存在节点没有被遍历，那么说明图中存在环，现在回头去看 BFS 的代码，你应该就很容易理解其中的逻辑了。
拓扑排序算法（BFS 版本）
如果你能看懂 BFS 版本的环检测算法，那么就很容易得到 BFS 版本的拓扑排序算法，因为节点的遍历顺序就是拓扑排序的结果。
比如刚才举的第一个例子，下图每个节点中的值即入队的顺序：
显然，这个顺序就是一个可行的拓扑排序结果。
所以，我们稍微修改一下 BFS 版本的环检测算法，记录节点的遍历顺序即可得到拓扑排序的结果：
// 主函数
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 建图，和环检测算法相同
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
// 计算入度，和环检测算法相同
int[] indgree = new int[numCourses];
for (int[] edge : prerequisites) {
int from = edge[1], to = edge[0];
indgree[to]++;
}
// 根据入度初始化队列中的节点，和环检测算法相同
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indgree[i] == 0) {
q.offer(i);
}
}
// 记录拓扑排序结果
int[] res = new int[numCourses];
// 记录遍历节点的顺序（索引）
int count = 0;
// 开始执行 BFS 算法
while (!q.isEmpty()) {
int cur = q.poll();
// 弹出节点的顺序即为拓扑排序结果
res[count] = cur;
count++;
for (int next : graph[cur]) {
indgree[next]--;
if (indgree[next] == 0) {
q.offer(next);
}
}
}
if (count != numCourses) {
// 存在环，拓扑排序不存在
return new int[]{};
}
return res;
}
// 建图函数
List<Integer>[] buildGraph(int n, int[][] edges) {
// 见前文
}
按道理，图的遍历 都需要 visited 数组防止走回头路，这里的 BFS 算法其实是通过 indegree 数组实现的 visited 数组的作用，只有入度为 0 的节点才能入队，从而保证不会出现死循环。
好了，到这里环检测算法、拓扑排序算法的 BFS 实现也讲完了，继续留一个思考题：
对于 BFS 的环检测算法，如果问你形成环的节点具体是哪些，你应该如何实现呢？
————————————
本文就讲到这里，后台回复「目录」可查看精选文章目录，回复「PDF」可下载刷题三件套，更多高质量课程见公众号菜单！