拓扑排序 —— 2. 力扣刷题207. 课程表

题目链接：https://leetcode.cn/problems/course-schedule/description/
题目难度：中等
相关标签：拓扑排序 / 广度优先搜搜 BFS / 深度优先搜索 DFS

2.1 问题与分析

2.1.1 原题截图

2.1.2 题目分析

首先，理解题目后必须马上意识到考察的是 图论类型中的有向图问题，接着考虑到有向图之间的关系，可以想到我们在本系列第一篇 博客 提到的 拓扑排序。

接着，这里将题目进一步简化：

给你 numCourses 门课程，和若干课程依赖关系 prerequisites，问你能否顺利修完所有课程。

换句话说：

• 每门课程是一个节点。

• 依赖关系是一个有向边（比如 [1, 0] 表示：想学 1，必须先学 0）。

这就构成了一个有向图，问题变成了：

这个图有没有环？

• 有环 = 某些课程互相依赖，永远无法完成。

• 无环 = 可以通过拓扑排序找到学习顺序。

在本系列的第一篇博客已经提到过，拓扑排序可以用来解决 判断有向图中是否有环问题。

最后已经大概怎么知道解决问题了，那么请回答这个问题 如何通过拓扑排序解决有向图中是否有环问题。

2.2 解法 1 —— 基于广度优先搜索（BFS）的拓扑排序（Kahn 算法）

不急着写代码，我们先用文字的形式，描述清楚解题思路。

2.2.1 解题思路

解题思路：

1. 构建图结构，使用二维数组存储，记作 graph；
2. 统计每个结点的入度，使用一维数组存储，记作 inCounts
3. 维护一个队列 Q，将 inCounts 中入度为 0 的元素入队；
4. 基于队列进行操作，将访问的结点存储到 results 数组中。
   a. 对于队中每个元素 e，将它的相邻结点的入度 减 1；
   b. 如果 减 1 后的结点入度为 0，加入队列 Q；
   c. 将 e 写入 results 数组。
   d. e 出列，循环此项操作。
5. 判定 results 数组长度是否与所有元素数目相等。相等表示可以正常访问所有结点，原拓扑 无环，返回 true，否则返回 false。

复杂度分析：

• 时间复杂度: O(n+m)，其中 n 为课程数，m 为先修课程的要求数。
• 空间复杂度: O(n+m)。

2.2.2 代码实现

前面已经将解题方法写明白了，写代码就很方便了，我们分别使用 C++ / python 与 java 三种语言实现。

基于 C++ 的代码实现

实现思路请参考前文，先理解思路再看代码。

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> inCount(numCourses);vector<vector<int>> graph(numCourses);// [0, 1] 表示，需要先学习课程 1，才能学习课程 0// Step 1: 构建图// Step 2: 统计入度for (const auto& par: prerequisites) {graph[par[1]].push_back(par[0]);inCount[par[0]]++;}// Step 3: 初始化队列queue<int> Q;for (int i=0; i<numCourses; i++) {if (inCount[i] == 0) {Q.push(i);}}// Step 4:vector<int> results;while (!Q.empty()) {auto front = Q.front();Q.pop();results.push_back(front);for (auto v: graph[front]) {inCount[v]--;if (inCount[v] == 0) {Q.push(v);}}}return results.size() == numCourses;}
};

基于 python 的代码实现

实现思路请参考前文，先理解思路再看代码。

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:inCount = [0] * numCoursesgraph = [[] for _ in range(numCourses)]# [0, 1] 表示，需要先学习课程 1，才能学习课程 0# Step 1: 构建图# Step 2: 统计入度for par in prerequisites:graph[par[1]].append(par[0])inCount[par[0]] += 1# Step 3: 初始化队列Q = deque()for i in range(numCourses):if inCount[i] == 0:Q.append(i)# Step 4:results = []while Q:front = Q.popleft()results.append(front)for v in graph[front]:inCount[v] -= 1if inCount[v] == 0:Q.append(v)return len(results) == numCourses

基于 java 的代码实现

实现思路请参考前文，先理解思路再看代码。

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] inCount = new int[numCourses];List<List<Integer>> graph = new ArrayList<>();for (int i = 0; i < numCourses; i++) {graph.add(new ArrayList<>());}// [0, 1] 表示，需要先学习课程 1，才能学习课程 0// Step 1: 构建图// Step 2: 统计入度for (int[] par : prerequisites) {graph.get(par[1]).add(par[0]);inCount[par[0]]++;}// Step 3: 初始化队列Queue<Integer> Q = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inCount[i] == 0) {Q.offer(i);}}// Step 4:List<Integer> results = new ArrayList<>();while (!Q.isEmpty()) {int front = Q.poll();results.add(front);for (int v : graph.get(front)) {inCount[v]--;if (inCount[v] == 0) {Q.offer(v);}}}return results.size() == numCourses;}
}

2.3 解法 2 —— 基于深度优先搜索（DFS）的拓扑排序

前面已经将解题方法写明白了，写代码就很方便了，我们分别使用 C++ / python 与 java 三种语言实现。

2.3.1 解题思路

解题思路：

1. 构建图，使用二维数组 graph 保存图的结构；
2. 初始化过程：
   a. 初始化一维数组 visited，它的每个元素含有三个状态 0 表示未访问过，1 表示已经访问过，2 表示已经记录到最终结果数组中。注意这个地方必须保证更新顺序，也就是 0 -> 1 -> 2。
   b. 初始化 valid 变量，表示DFS过程中是否遇到 环，比如遇到环了就结束。
   c. 初始化 results 数组，用于记录已经访问过的路径。
3. DFS 过程，该过程对每一个未访问过的结点进行考察，对于结点 e，完成操作包括：
   a. 更新 visited 数组，标记 e 结点已经被访问过。
   b. DFS 访问与 e 结点连接的其他结点。
   c. 如果下一个结点 visited 状态为 0， 则继续DFS；如果状态为 2，则说明有环，更新 valid 结束 DFS。
   d. 访问 e 结点的所有相邻结点后，将 e 记录到 results 中。
   e. 访问 e 结点以后，更新 visited[e] 的状态为 2，表示已经记录到 results 数组中。
4. 判定 results 数组长度是否与所有元素数目相等。相等表示可以正常访问所有结点，原拓扑 无环，返回 true，否则返回 false。

2.3.2 代码实现

基于 C++ 的代码实现

实现思路请参考前文，先理解思路再看代码。

class Solution {
private:bool valid = true;vector<int> visited;vector<int> results;vector<vector<int>> graph;void dfs(int i) {visited[i] = 1;for (auto v: graph[i]) {if (visited[v] == 0) {dfs(v);} else if (visited[v] == 1) {valid = false;return;}}results.push_back(i);visited[i] = 2;}
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {graph = vector<vector<int>>(numCourses);for (const auto& par: prerequisites) {graph[par[1]].push_back(par[0]);}visited = vector<int>(numCourses, 0);for (int i=0; i<numCourses && valid; i++) {if (visited[i] == 0) {dfs(i);}}return results.size() == numCourses;}
};

基于 python 的代码实现

实现思路请参考前文，先理解思路再看代码。

class Solution:def __init__(self):self.valid = Trueself.visited = []self.results = []self.graph = []def dfs(self, i: int):self.visited[i] = 1for v in self.graph[i]:if self.visited[v] == 0:self.dfs(v)if not self.valid:returnelif self.visited[v] == 1:self.valid = Falsereturnself.results.append(i)self.visited[i] = 2def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:self.graph = [[] for _ in range(numCourses)]for par in prerequisites:self.graph[par[1]].append(par[0])self.visited = [0] * numCoursesself.results = []self.valid = Truefor i in range(numCourses):if self.valid and self.visited[i] == 0:self.dfs(i)return len(self.results) == numCourses

基于 java 的代码实现

实现思路请参考前文，先理解思路再看代码。

class Solution {private boolean valid = true;private int[] visited;private List<Integer> results;private List<List<Integer>> graph;private void dfs(int i) {visited[i] = 1;for (int v : graph.get(i)) {if (visited[v] == 0) {dfs(v);if (!valid) return;} else if (visited[v] == 1) {valid = false;return;}}results.add(i);visited[i] = 2;}public boolean canFinish(int numCourses, int[][] prerequisites) {graph = new ArrayList<>();for (int i = 0; i < numCourses; i++) {graph.add(new ArrayList<>());}for (int[] par : prerequisites) {graph.get(par[1]).add(par[0]);}visited = new int[numCourses];results = new ArrayList<>();valid = true;for (int i = 0; i < numCourses && valid; i++) {if (visited[i] == 0) {dfs(i);}}return results.size() == numCourses;}
}

2.4 总结

力扣的这道题可以作为 拓扑排序 的 模板题，因为理解题目容易，必须建立在对 拓扑排序 的两种方法的了解的基础上，才能完成。中等难度，比较适合新手练习。

就题目而言，这道题本身就是判断是否有环的问题，通过拓扑排序实现而言。

继续强调一下，做题的目的是为了更加熟悉拓扑排序的算法思想，算法套路，不能停留在解决问题本身。

感谢各位小伙伴们的 阅读、点赞、评论 与 关注 ~ 希望本文能帮助到各位，共勉 ~

Smileyan
2025.04.12 19:04