环检测及拓扑排序算法

labuladong约 15714 字大约 52 分钟数据结构图论算法

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

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

LeetCode	力扣	难度
207. Course Scheduleopen in new window	207. 课程表open in new window	🟠
210. Course Schedule IIopen in new window	210. 课程表 IIopen in new window	🟠
-	剑指 Offer II 113. 课程顺序open in new window	🟠

Tip

本文有视频版：拓扑排序详解及应用open in new window。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

图这种数据结构有一些比较特殊的算法，比如二分图判断，有环图无环图的判断，拓扑排序，以及最经典的最小生成树，单源最短路径问题，更难的就是类似网络流这样的问题。

不过以我的经验呢，像网络流这种问题，你又不是打竞赛的，没时间的话就没必要学了；像最小生成树和最短路径问题，虽然从刷题的角度用到的不多，但它们属于经典算法，学有余力可以掌握一下；像二分图判定、拓扑排序这一类，属于比较基本且有用的算法，应该比较熟练地掌握。

那么本文就结合具体的算法题，来说两个图论算法：有向图的环检测、拓扑排序算法。

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

环检测算法（DFS 版本）

先来看看力扣第 207 题「课程表open in new window」：

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] 中的所有课程对 互不相同

函数签名如下：

boolean canFinish(int numCourses, int[][] prerequisites);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

bool canFinish(int numCourses, vector<vector<int>>& prerequisites);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

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

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var canFinish = function(numCourses, prerequisites);

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

其实这种场景在现实生活中也十分常见，比如我们写代码 import 包也是一个例子，必须合理设计代码目录结构，否则会出现循环依赖，编译器会报错，所以编译器实际上也使用了类似算法来判断你的代码是否能够成功编译。

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

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

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

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

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

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

如何转换成图呢？我们前文图论基础写过图的两种存储形式，邻接矩阵和邻接表。

以我刷题的经验，常见的存储方式是使用邻接表，比如下面这种结构：

List<Integer>[] graph;

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

vector<int> graph[];

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

graph = List[int]()

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var graph []List[int]

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var graph = []; // Array of List<Integer>

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;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

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

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

def buildGraph(numCourses: int, prerequisites: List[List[int]]) -> List[List[int]]:
    # 图中共有 numCourses 个节点
    graph = [[] for _ in range(numCourses)]
    for edge in prerequisites:
        from_, to_ = edge[1], edge[0]
        # 添加一条从 from 指向 to 的有向边
        # 边的方向是「被依赖」关系，即修完课程 from 才能修课程 to
        graph[from_].append(to_)
    return graph

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

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

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var buildGraph = function(numCourses, prerequisites) {
    // 图中共有 numCourses 个节点
    var graph = new Array(numCourses);
    for (var i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList();
    }
    for (var j = 0; j < prerequisites.length; j++) {
        var edge = prerequisites[j];
        var 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);
    }
    /* 后序遍历代码位置 */
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 防止重复遍历同一个节点
vector<bool> visited;
// 从节点 s 开始 DFS 遍历，将遍历过的节点标记为 true
void traverse(vector<int>* graph, int s) {
    if (visited[s]) {
        return;
    }
    /* 前序遍历代码位置 */
    // 将当前节点标记为已遍历
    visited[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    /* 后序遍历代码位置 */
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

visited = []

# 从节点s开始DFS遍历，将遍历过的节点标记为True
def traverse(graph, s):
    if visited[s]:
        return
    # 前序遍历代码位置
    # 将当前节点标记为已遍历
    visited[s] = True
    for t in graph[s]:
        traverse(graph, t)
    # 后序遍历代码位置

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 防止重复遍历同一个节点
var visited []bool

// 从节点 s 开始 DFS 遍历，将遍历过的节点标记为 true
func traverse(graph []list.List, s int) {
	if visited[s] {
		return
	}

	// 前序遍历代码位置
	visited[s] = true

	for e := graph[s].Front(); e != nil; e = e.Next() {
		traverse(graph, e.Value.(int))
	}
	// 后序遍历代码位置
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var visited = [];
function traverse(graph, s) {
    if (visited[s]) {
        return;
    }
    /* 前序遍历代码位置 */
    visited[s] = true;
    for (var i = 0; i < graph[s].length; i++) {
        traverse(graph, graph[s][i]);
    }
    /* 后序遍历代码位置 */
}

那么我们就可以直接套用这个遍历代码：

// 防止重复遍历同一个节点
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) {
    // 代码见上文
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 防止重复遍历同一个节点
vector<bool> visited;

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
    
    visited = vector<bool>(numCourses, false);
    for (int i = 0; i < numCourses; i++) {
        traverse(graph, i);
    }
}

void traverse(vector<vector<int>>& graph, int s) {
    // 代码见上文
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

visited: List[bool]

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = buildGraph(numCourses, prerequisites)
    global visited
    visited = [False] * numCourses
    for i in range(numCourses):
        traverse(graph, i)

def traverse(graph: List[List[int]], s: int) -> None:
    # 代码见上文
    pass

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var visited []bool

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := buildGraph(numCourses, prerequisites)
    
    visited = make([]bool, numCourses)
    for i := 0; i < numCourses; i++ {
        traverse(graph, i)
    }
}

func traverse(graph []int, s int) {
    // 代码见上文
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var visited;

function canFinish(numCourses, prerequisites) {
    var graph = buildGraph(numCourses, prerequisites);

    visited = new Array(numCourses).fill(false);

    for (var i = 0; i < numCourses; i++) {
        traverse(graph, i);
    }
}

function traverse(graph, 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;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

vector<bool> onPath;
vector<bool> visited;

bool hasCycle = false;

void traverse(vector<int>* 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;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

onPath = []
visited = []
hasCycle = False

def traverse(graph: List[list], s: int) -> None:
    global hasCycle
    if onPath[s]:
        # 发现环！！！
        hasCycle = True
    if visited[s] or hasCycle:
        return
    # 将节点 s 标记为已遍历
    visited[s] = True
    # 开始遍历节点 s
    onPath[s] = True
    for t in graph[s]:
        traverse(graph, t)
    # 节点 s 遍历完成
    onPath[s] = False

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var onPath []bool
var visited []bool
var hasCycle bool

func traverse(graph [][]int, s int) {
    if onPath[s] {
        // 发现环！！！
        hasCycle = true
    }
    if visited[s] || hasCycle {
        return
    }
    // 将节点 s 标记为已遍历
    visited[s] = true
    // 开始遍历节点 s
    onPath[s] = true
    for _, t := range *graph[s] {
        traverse(graph, t)
    }
    // 节点 s 遍历完成
    onPath[s] = false
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var onPath = [];
var visited = [];

var hasCycle = false;

function traverse(graph, s) {
    if (onPath[s]) {
        // 发现环！！！
        hasCycle = true;
    }
    if (visited[s] || hasCycle) {
        return;
    }
    // 将节点 s 标记为已遍历
    visited[s] = true;
    // 开始遍历节点 s
    onPath[s] = true;
    for (var i = 0; i < graph[s].length; i++) {
        traverse(graph, graph[s][i]);
    }
    // 节点 s 遍历完成
    onPath[s] = false;
}

这里就有点回溯算法的味道了，在进入节点 s 的时候将 onPath[s] 标记为 true，离开时标记回 false，如果发现 onPath[s] 已经被标记，说明出现了环。

注意 visited 数组和 onPath 数组的区别，因为二叉树算是特殊的图，所以用遍历二叉树的过程来理解下这两个数组的区别：

上述 GIF 描述了递归遍历二叉树的过程，在 visited 中被标记为 true 的节点用灰色表示，在 onPath 中被标记为 true 的节点用绿色表示。

Tip

类比贪吃蛇游戏，visited 记录蛇经过过的格子，而 onPath 仅仅记录蛇身。onPath 用于判断是否成环，类比当贪吃蛇自己咬到自己（成环）的场景。

这样，就可以在遍历图的过程中顺便判断是否存在环了，完整代码如下：

class Solution {
    // 记录一次递归堆栈中的节点
    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;/**<extend up -150><div class="img-content"><img src="/algo/images/拓扑排序/4.jpeg" class="myimage"/></div> */
        }
        
        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) {
        // 代码见前文
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    // 记录一次递归堆栈中的节点
    vector<bool> onPath;
    // 记录遍历过的节点，防止走回头路
    vector<bool> visited;
    // 记录图中是否有环
    bool hasCycle = false;

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph = buildGraph(numCourses, prerequisites);

        visited = vector<bool>(numCourses);
        onPath = vector<bool>(numCourses);

        for (int i = 0; i < numCourses; i++) {
            // 遍历图中的所有节点
            traverse(graph, i);
        }
        // 只要没有循环依赖可以完成所有课程
        return !hasCycle;
    }

    void traverse(vector<vector<int>>& graph, int s) {
        if (onPath[s]) {
            // 出现环
            hasCycle = true;/**<extend up -150><div class="img-content"><img src="/algo/images/拓扑排序/4.jpeg" class="myimage"/></div> */
        }

        if (visited[s] || hasCycle) {
            // 如果已经找到了环，也不用再遍历了
            return;
        }
        // 前序代码位置
        visited[s] = true;
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        // 后序代码位置
        onPath[s] = false;
    }

    vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
        // 代码见前文
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = self.buildGraph(numCourses, prerequisites)
        self.visited = [False] * numCourses
        self.onPath = [False] * numCourses
        self.hasCycle = False
        for i in range(numCourses):
            self.traverse(graph, i)
        return not self.hasCycle
    
    def traverse(self, graph, s):
        if self.onPath[s]:
            self.hasCycle = True
        if self.visited[s] or self.hasCycle:
            return
        self.visited[s] = True
        self.onPath[s] = True
        for t in graph[s]:
            self.traverse(graph, t)
        self.onPath[s] = False
    
    def buildGraph(self, numCourses, prerequisites):
        # 代码见前文

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func canFinish(numCourses int, prerequisites [][]int) bool {
    // 记录一次递归堆栈中的节点
    onPath := make([]bool, numCourses)
    // 记录遍历过的节点，防止走回头路
    visited := make([]bool, numCourses)
    // 记录图中是否有环
    hasCycle := false

    graph := buildGraph(numCourses, prerequisites)

    for i := 0; i < numCourses; i++ {
        // 遍历图中的所有节点
        traverse(graph, i, &visited, &onPath, &hasCycle)
    }
    // 只要没有循环依赖可以完成所有课程
    return !hasCycle
}

func traverse(graph [][]int, s int, visited *[]bool, onPath *[]bool, hasCycle *bool) {
    if (*onPath)[s] {
        // 出现环
        *hasCycle = true/**<extend up -150><div class="img-content"><img src="/algo/images/拓扑排序/4.jpeg" class="myimage"/></div> */
        return
    }

    if (*visited)[s] || *hasCycle {
        // 如果已经找到了环，也不用再遍历了
        return
    }

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

func buildGraph(numCourses int, prerequisites [][]int) [][]int {
    // 代码略
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var canFinish = function(numCourses, prerequisites) {
    // 记录一次递归堆栈中的节点
    var onPath = new Array(numCourses).fill(false);
    // 记录遍历过的节点，防止走回头路
    var visited = new Array(numCourses).fill(false);
    // 记录图中是否有环
    var hasCycle = false;

    function traverse(graph, s) {
        if (onPath[s]) {
            // 出现环
            hasCycle = true;/**<extend up -150><div class="img-content"><img src="/algo/images/拓扑排序/4.jpeg" class="myimage"/></div> */
        }
        
        if (visited[s] || hasCycle) {
            // 如果已经找到了环，也不用再遍历了
            return;
        }
        // 前序代码位置
        visited[s] = true;
        onPath[s] = true;
        graph[s].forEach(t => traverse(graph, t));
        // 后序代码位置
        onPath[s] = false;
    }

    function buildGraph(numCourses, prerequisites) {
        // 代码见前文
    }

    var graph = buildGraph(numCourses, prerequisites);
    visited = new Array(numCourses).fill(false);
    onPath = new Array(numCourses).fill(false);
    
    for (var i = 0; i < numCourses; i++) {
        // 遍历图中的所有节点
        traverse(graph, i);
    }
    // 只要没有循环依赖可以完成所有课程
    return !hasCycle;
};

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

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

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

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

这个问题留给大家思考，我会在公众号留言区置顶正确的答案。

那么接下来，我们来再讲一个经典的图算法：拓扑排序。

拓扑排序算法（DFS 版本）

看下力扣第 210 题「课程表 IIopen in new window」：

210. 课程表 II | 力扣 | LeetCode |

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [a_i, b_i] ，表示在选修课程 a_i 前必须先选修 b_i 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
a_i != b_i
所有[a_i, b_i] 互不相同

这道题就是上道题的进阶版，不是仅仅让你判断是否可以完成所有课程，而是进一步让你返回一个合理的上课顺序，保证开始修每个课程时，前置的课程都已经修完。

函数签名如下：

int[] findOrder(int numCourses, int[][] prerequisites);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

int* findOrder(int numCourses, int** prerequisites);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func findOrder(numCourses int, prerequisites [][]int) []int

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var findOrder = function(numCourses, prerequisites) {};

这里我先说一下拓扑排序（Topological Sorting）这个名词，网上搜出来的定义很数学，这里干脆用百度百科的一幅图来让你直观地感受下：

Note

图片中拓扑排序的结果有误，C7->C8->C6 应该改为 C6->C7->C8。

直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的，比如上图所有箭头都是朝右的。

很显然，如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。

但是我们这道题和拓扑排序有什么关系呢？

其实也不难看出来，如果把课程抽象成节点，课程之间的依赖关系抽象成有向边，那么这幅图的拓扑排序结果就是上课顺序。

首先，我们先判断一下题目输入的课程依赖是否成环，成环的话是无法进行拓扑排序的，所以我们可以复用上一道题的主函数：

public int[] findOrder(int numCourses, int[][] prerequisites) {
    if (!canFinish(numCourses, prerequisites)) {
        // 不可能完成所有课程
        return new int[]{};
    }
    // ...
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    if (!canFinish(numCourses, prerequisites)) {
        // 不可能完成所有课程
        return vector<int>();
    }
    // ...
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    if not canFinish(numCourses, prerequisites):
        # 不可能完成所有课程
        return []
    # ...

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func findOrder(numCourses int, prerequisites [][]int) []int {
    if !canFinish(numCourses, prerequisites) {
        // 不可能完成所有课程
        return []int{}
    }
    // ...
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var findOrder = function(numCourses, prerequisites) {
    if (!canFinish(numCourses, prerequisites)) {
        // 不可能完成所有课程
        return [];
    }
    // ...
}

那么关键问题来了，如何进行拓扑排序？是不是又要秀什么高大上的技巧了？

其实特别简单，将后序遍历的结果进行反转，就是拓扑排序的结果。

Note

有的读者提到，他在网上看到的拓扑排序算法不用对后序遍历结果进行反转，这是为什么呢？

你确实可以看到这样的解法，原因是他建图的时候对边的定义和我不同。我建的图中箭头方向是「被依赖」关系，比如节点 1 指向 2，含义是节点 1 被节点 2 依赖，即做完 1 才能去做 2，

如果你反过来，把有向边定义为「依赖」关系，那么整幅图中边全部反转，就可以不对后序遍历结果反转。具体来说，就是把我的解法代码中 graph[from].add(to); 改成 graph[to].add(from); 就可以不反转了。

不过呢，现实中一般都是从初级任务指向进阶任务，所以像我这样把边定义为「被依赖」关系可能比较符合我们的认知习惯。

直接看解法代码吧，在上一题环检测的代码基础上添加了记录后序遍历结果的逻辑：

class Solution {
    // 记录后序遍历结果
    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) {
        // 代码见前文
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    // 记录后序遍历结果
    vector<int> postorder;
    // 记录是否存在环
    bool hasCycle = false;
    vector<bool> visited, onPath;

    // 主函数
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
        visited = vector<bool>(numCourses, false);
        onPath = vector<bool>(numCourses, false);
        // 遍历图
        for (int i = 0; i < numCourses; i++) {
            traverse(graph, i);
        }
        // 有环图无法进行拓扑排序
        if (hasCycle) {
            return {};
        }
        // 逆后序遍历结果即为拓扑排序结果
        reverse(postorder.begin(), postorder.end());
        vector<int> res(numCourses);
        for (int i = 0; i < numCourses; i++) {
            res[i] = postorder[i];
        }
        return res;
    }

    // 图遍历函数
    void traverse(vector<vector<int>>& 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.push_back(s);
        onPath[s] = false;
    }

    // 建图函数
    vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
        // 代码见前文。
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 记录后序遍历结果
        postorder = []
        # 记录是否存在环
        hasCycle = [False]
        visited = [False] * numCourses
        onPath = [False] * numCourses

        # 建图函数
        def buildGraph(numCourses, prerequisites):
            # 代码见前文
            pass

        # 图遍历函数
        def traverse(graph, s):
            if onPath[s]:
                # 发现环
                hasCycle[0] = True
            if visited[s] or hasCycle[0]:
                return
            # 前序遍历位置
            onPath[s] = True
            visited[s] = True
            for t in graph[s]:
                traverse(graph, t)
            # 后序遍历位置
            postorder.append(s)
            onPath[s] = False

        graph = buildGraph(numCourses, prerequisites)
        # 遍历图
        for i in range(numCourses):
            traverse(graph, i)
        # 有环图无法进行拓扑排序
        if hasCycle[0]:
            return []
        # 逆后序遍历结果即为拓扑排序结果
        postorder.reverse()
        res = []
        for i in postorder:
            res.append(i)
        return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func findOrder(numCourses int, prerequisites [][]int) []int {
    // 后序遍历结果
    postorder := []int{}
    // 是否存在环
    hasCycle := false
    // 节点访问状态
    visited := make([]bool, numCourses)
    // 节点遍历状态
    onPath := make([]bool, numCourses)

    // 构建图
    graph := buildGraph(numCourses, prerequisites)

    // 遍历图
    for i := 0; i < numCourses; i++ {
        traverse(graph, i, &postorder, &hasCycle, visited, onPath)
    }

    // 如果有环，返回空
    if hasCycle {
        return []int{}
    }

    // 逆序后序遍历结果
    reverse(postorder)

    return postorder
}

// 拓扑排序图遍历函数
func traverse(graph [][]int, s int, postorder *[]int, hasCycle *bool, visited []bool, onPath []bool) {
    // 如果当前节点在当前遍历路径中已经访问过，说明存在环
    if onPath[s] {
        *hasCycle = true
    }

    // 如果当前节点已经被访问过或者存在环，则退出遍历
    if visited[s] || *hasCycle {
        return
    }

    // 将当前节点标记为已经在当前遍历路径中
    onPath[s] = true
    // 标记当前节点已经被访问
    visited[s] = true

    // 遍历当前节点的所有邻接节点
    for _, t := range graph[s] {
        traverse(graph, t, postorder, hasCycle, visited, onPath)
    }

    // 将当前节点加入后序遍历结果
    *postorder = append(*postorder, s)
    // 将当前节点标记为已经不在当前遍历路径中
    onPath[s] = false
}

// 建图函数
func buildGraph(numCourses int, prerequisites [][]int) [][]int {
    // 实现见前文
}

// 数组翻转函数
func reverse(arr []int) {
    for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
        arr[i], arr[j] = arr[j], arr[i]
    }
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var findOrder = function(numCourses, prerequisites) {
    // 记录后序遍历结果
    const postorder = [];
    // 记录是否存在环
    let hasCycle = false;
    const visited = new Array(numCourses).fill(false);
    const onPath = new Array(numCourses).fill(false);

    // 图遍历函数
    const traverse = function(graph, s) {
        if (onPath[s]) {
            // 发现环
            hasCycle = true;
        }
        if (visited[s] || hasCycle) {
            return;
        }
        // 前序遍历位置
        onPath[s] = true;
        visited[s] = true;
        for (let t of graph[s]) {
            traverse(graph, t);
        }
        // 后序遍历位置
        postorder.push(s);
        onPath[s] = false;
    }

    // 建图函数
    const buildGraph = function(numCourses, prerequisites) {
        // 代码见前文
    }

    const graph = buildGraph(numCourses, prerequisites);
    // 遍历图
    for (let i = 0; i < numCourses; i++) {
        traverse(graph, i);
    }
    // 有环图无法进行拓扑排序
    if (hasCycle) {
        return [];
    }
    // 逆后序遍历结果即为拓扑排序结果
    postorder.reverse();
    return postorder;
};

代码虽然看起来多，但是逻辑应该是很清楚的，只要图中无环，那么我们就调用 traverse 函数对图进行 DFS 遍历，记录后序遍历结果，最后把后序遍历结果反转，作为最终的答案。

那么为什么后序遍历的反转结果就是拓扑排序呢？

我这里也避免数学证明，用一个直观地例子来解释，我们就说二叉树，这是我们说过很多次的二叉树遍历框架：

void traverse(TreeNode root) {
    // 前序遍历代码位置
    traverse(root.left)
    // 中序遍历代码位置
    traverse(root.right)
    // 后序遍历代码位置
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

void traverse(TreeNode* root) {
    // 前序遍历代码位置
    traverse(root->left);
    // 中序遍历代码位置
    traverse(root->right);
    // 后序遍历代码位置
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def traverse(root: TreeNode):
    # 前序遍历代码位置
    traverse(root.left)
    # 中序遍历代码位置
    traverse(root.right)
    # 后序遍历代码位置

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func traverse(root *TreeNode) {
    // 前序遍历代码位置

    traverse(root.left)

    // 中序遍历代码位置

    traverse(root.right)

    // 后序遍历代码位置
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var traverse = function(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[] 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);/**<extend down -200><div class="img-content"><img src="/algo/images/拓扑排序/6.jpeg" class="myimage"/></div> */
        }
    }

    // 记录遍历的节点个数
    int count = 0;
    // 开始执行 BFS 循环
    while (!q.isEmpty()) {
        // 弹出节点 cur，并将它指向的节点的入度减一
        int cur = q.poll();
        count++;
        for (int next : graph[cur]) {/**<extend up -200><div class="img-content"><img src="/algo/images/拓扑排序/7.jpeg" class="myimage"/></div> */
            indegree[next]--;
            if (indegree[next] == 0) {
                // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                q.offer(next);
            }
        }
    }

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


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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

#include<vector>
#include<queue>

using namespace std;

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

    // 根据入度初始化队列中的节点
    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            // 节点 i 没有入度，即没有依赖的节点
            // 可以作为拓扑排序的起点，加入队列
            q.push(i);/**<extend down -200><div class="img-content"><img src="/algo/images/拓扑排序/6.jpeg" class="myimage"/></div> */
        }
    }

    // 记录遍历的节点个数
    int count = 0;
    // 开始执行 BFS 循环
    while (!q.empty()) {
        // 弹出节点 cur，并将它指向的节点的入度减一
        int cur = q.front();
        q.pop();
        count++;
        for (int next : graph[cur]) {/**<extend up -200><div class="img-content"><img src="/algo/images/拓扑排序/7.jpeg" class="myimage"/></div> */
            indegree[next]--;
            if (indegree[next] == 0) {
                // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                q.push(next);
            }
        }
    }

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


// 建图函数
vector<vector<int>> buildGraph(int n, vector<vector<int>>& edges) {
    // 见前文
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List
from collections import deque

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    # 建图，有向边代表「被依赖」关系
    graph = buildGraph(numCourses, prerequisites)
    # 构建入度数组
    indegree = [0] * numCourses
    for edge in prerequisites:
        from_node, to_node = edge[1], edge[0]
        # 节点 to_node 的入度加一
        indegree[to_node] += 1

    # 根据入度初始化队列中的节点
    q = deque()
    for i in range(numCourses):
        if indegree[i] == 0:
            # 节点 i 没有入度，即没有依赖的节点
            # 可以作为拓扑排序的起点，加入队列
            q.append(i)

    # 记录遍历的节点个数
    count = 0
    # 开始执行 BFS 循环
    while q:
        # 弹出节点 cur，并将它指向的节点的入度减一
        cur = q.popleft()
        count += 1
        for next_node in graph[cur]:
            indegree[next_node] -= 1
            if indegree[next_node] == 0:
                # 如果入度变为 0，说明 next_node 依赖的节点都已被遍历
                q.append(next_node)

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

# 建图函数
def buildGraph(n: int, edges: List[List[int]]) -> List[List[int]]:
    # 见前文
    pass

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func canFinish(numCourses int, prerequisites [][]int) bool {
    // 建图，有向边代表「被依赖」关系
    graph := buildGraph(numCourses, prerequisites)
    // 构建入度数组
    indegree := make([]int, numCourses)
    for _, edge := range prerequisites {
        from, to := edge[1], edge[0]
        // 节点 to 的入度加一
        indegree[to]++
    }

    // 根据入度初始化队列中的节点
    q := make([]int, 0)
    for i := 0; i < numCourses; i++ {
        if indegree[i] == 0 {
            // 节点 i 没有入度，即没有依赖的节点
            // 可以作为拓扑排序的起点，加入队列
            q = append(q, i)/**<extend down -200><div class="img-content"><img src="/algo/images/拓扑排序/6.jpeg" class="myimage"/></div> */
        }
    }

    // 记录遍历的节点个数
    count := 0
    // 开始执行 BFS 循环
    for len(q) > 0 {
        // 弹出节点 cur，并将它指向的节点的入度减一
        cur := q[0]
        q = q[1:]
        count++
        for _, next := range graph[cur] {/**<extend up -200><div class="img-content"><img src="/algo/images/拓扑排序/7.jpeg" class="myimage"/></div> */
            indegree[next]--
            if indegree[next] == 0 {
                // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                q = append(q, next)
            }
        }
    }

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

// 建图函数
func buildGraph(n int, edges [][]int) []int {
    // 见前文
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var canFinish = function(numCourses, prerequisites) {
    // 建图，有向边代表「被依赖」关系
    let graph = buildGraph(numCourses, prerequisites);
    // 构建入度数组
    let indegree = new Array(numCourses).fill(0);
    for (let edge of prerequisites) {
        let from = edge[1], to = edge[0];
        // 节点 to 的入度加一
        indegree[to]++;
    }

    // 根据入度初始化队列中的节点
    let q = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            // 节点 i 没有入度，即没有依赖的节点
            // 可以作为拓扑排序的起点，加入队列
            q.push(i);/**<extend down -200><div class="img-content"><img src="/algo/images/拓扑排序/6.jpeg" class="myimage"/></div> */
        }
    }

    // 记录遍历的节点个数
    let count = 0;
    // 开始执行 BFS 循环
    while (q.length > 0) {
        // 弹出节点 cur，并将它指向的节点的入度减一
        let cur = q.shift();
        count++;
        for (let next of graph[cur]) {/**<extend up -200><div class="img-content"><img src="/algo/images/拓扑排序/7.jpeg" class="myimage"/></div> */
            indegree[next]--;
            if (indegree[next] == 0) {
                // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                q.push(next);
            }
        }
    }

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


// 建图函数
function buildGraph(n, 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[] indegree = new int[numCourses];
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        indegree[to]++;
    }

    // 根据入度初始化队列中的节点，和环检测算法相同
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            q.offer(i);/**<extend up -200><div class="img-content"><img src="/algo/images/拓扑排序/6.jpeg" class="myimage"/></div> */
        }
    }

    // 记录拓扑排序结果
    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]) {/**<extend up -200><div class="img-content"><img src="/algo/images/拓扑排序/7.jpeg" class="myimage"/></div> */
            indegree[next]--;
            if (indegree[next] == 0) {
                q.offer(next);
            }
        }
    }

    if (count != numCourses) {
        // 存在环，拓扑排序不存在
        return new int[]{};
    }
    
    return res;
}

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    // 建图，和环检测算法相同
    vector<vector<int>> graph(numCourses);
    for (auto edge : prerequisites) {
        int from = edge[1], to = edge[0];
        graph[from].push_back(to);
    }
    // 计算入度，和环检测算法相同
    vector<int> indegree(numCourses, 0);
    for (auto edge : prerequisites) {
        int from = edge[1], to = edge[0];
        indegree[to]++;
    }

    // 根据入度初始化队列中的节点，和环检测算法相同
    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            q.push(i);/**<extend up -200><div class="img-content"><img src="/algo/images/拓扑排序/6.jpeg" class="myimage"/></div> */
        }
    }

    // 记录拓扑排序结果
    vector<int> res;
    // 开始执行 BFS 算法
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        // 弹出节点的顺序即为拓扑排序结果
        res.push_back(cur);
        for (int next : graph[cur]) {/**<extend up -200><div class="img-content"><img src="/algo/images/拓扑排序/7.jpeg" class="myimage"/></div> */
            indegree[next]--;
            if (indegree[next] == 0) {
                q.push(next);
            }
        }
    }

    if (res.size() != numCourses) {
        // 存在环，拓扑排序不存在
        return vector<int>{};
    }
    
    return res;
}

// 建图函数
vector<vector<int>> buildGraph(int n, vector<vector<int>>& edges) {
    // 见前文
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    # 建图，和环检测算法相同
    graph = buildGraph(numCourses, prerequisites)
    # 计算入度，和环检测算法相同
    indegree = [0] * numCourses
    for edge in prerequisites:
        from_, to = edge[1], edge[0]
        indegree[to] += 1

    # 根据入度初始化队列中的节点，和环检测算法相同
    q = []
    for i in range(numCourses):
        if indegree[i] == 0:
            q.append(i)

    # 记录拓扑排序结果
    res = [0] * numCourses
    # 记录遍历节点的顺序（索引）
    count = 0
    # 开始执行 BFS 算法
    while q:
        cur = q.pop(0)
        # 弹出节点的顺序即为拓扑排序结果
        res[count] = cur
        count += 1
        for next_ in graph[cur]:
            indegree[next_] -= 1
            if indegree[next_] == 0:
                q.append(next_)

    if count != numCourses:
        # 存在环，拓扑排序不存在
        return []
    
    return res

# 建图函数
def buildGraph(n: int, edges: List[List[int]]) -> List[List[int]]:
    # 见前文

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func findOrder(numCourses int, prerequisites [][]int) []int {
    // 建图，和环检测算法相同
    graph := buildGraph(numCourses, prerequisites)
    // 计算入度，和环检测算法相同
    indegree := make([]int, numCourses)
    for _, edge := range prerequisites {
        from, to := edge[1], edge[0]
        indegree[to]++
    }

    // 根据入度初始化队列中的节点，和环检测算法相同
    q := make([]int, 0)
    for i, val := range indegree {
        if val == 0 {
            q = append(q, i)
        }
    }

    // 记录拓扑排序结果
    res := make([]int, numCourses)
    // 记录遍历节点的顺序（索引）
    count := 0
    // 开始执行 BFS 算法
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        // 弹出节点的顺序即为拓扑排序结果
        res[count] = cur
        count++
        for _, next := range graph[cur] {
            indegree[next]--
            if indegree[next] == 0 {
                q = append(q, next)
            }
        }
    }

    if count != numCourses {
        // 存在环，拓扑排序不存在
        return []int{}
    }

    return res
}

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

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var findOrder = function(numCourses, prerequisites) {
    var buildGraph = function(n, edges) {
        // See previous functions for code conversion
    }
    // 建图，和环检测算法相同
    let graph = buildGraph(numCourses, prerequisites);
    // 计算入度，和环检测算法相同
    let indegree = new Array(numCourses).fill(0);
    for (let i = 0; i < prerequisites.length; i++) {
        let edge = prerequisites[i];
        let from = edge[1], to = edge[0];
        indegree[to]++;
    }

    // 根据入度初始化队列中的节点，和环检测算法相同
    let q = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            q.push(i);/**<extend up -200><div class="img-content"><img src="/algo/images/拓扑排序/6.jpeg" class="myimage"/></div> */
        }
    }

    // 记录拓扑排序结果
    let res = new Array(numCourses);
    // 记录遍历节点的顺序（索引）
    let count = 0;
    // 开始执行 BFS 算法
    while (q.length > 0) {
        let cur = q.shift();
        // 弹出节点的顺序即为拓扑排序结果
        res[count] = cur;
        count++;
        for (let i = 0; i < graph[cur].length; i++) {
            let next = graph[cur][i];/**<extend up -200><div class="img-content"><img src="/algo/images/拓扑排序/7.jpeg" class="myimage"/></div> */
            indegree[next]--;
            if (indegree[next] == 0) {
                q.push(next);
            }
        }
    }

    if (count != numCourses) {
        // 存在环，拓扑排序不存在
        return [];
    }
    
    return res;
}

按道理，图的遍历都需要 visited 数组防止走回头路，这里的 BFS 算法其实是通过 indegree 数组实现的 visited 数组的作用，只有入度为 0 的节点才能入队，从而保证不会出现死循环。

好了，到这里环检测算法、拓扑排序算法的 BFS 实现也讲完了，继续留一个思考题：

对于 BFS 的环检测算法，如果问你形成环的节点具体是哪些，你应该如何实现呢？

引用本文的文章

Dijkstra 算法模板及应用 Kruskal 最小生成树算法 Prim 最小生成树算法二分图判定算法图论基础及遍历算法并查集（Union-Find）算法我的刷题心得用算法打败算法

引用本文的题目

安装我的 Chrome 刷题插件open in new window 点开下列题目可直接查看解题思路：

LeetCode	力扣
310. Minimum Height Treesopen in new window	310. 最小高度树open in new window
-	剑指 Offer II 113. 课程顺序open in new window

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 环检测算法（DFS 版本）

# 拓扑排序算法（DFS 版本）

# 环检测算法（BFS 版本）

# 拓扑排序算法（BFS 版本）

环检测算法（DFS 版本）

拓扑排序算法（DFS 版本）

环检测算法（BFS 版本）

拓扑排序算法（BFS 版本）