LeetCode 207｜课程表（Course Schedule）题解 – 拓扑排序判环法
题目描述
本题是一道典型的课程安排问题，题目大意如下：
你这个学期必须选修numCourses门课程，记为0到numCourses - 1。
某些课程有先修课程要求，先修课程以数组prerequisites给出，其中prerequisites[i] = [a_i, b_i]表示：
想学习课程
a_i，你必须先完成课程b_i。
请你判断是否可能完成所有课程的学习。如果可以，返回true；否则返回false。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程，学习课程 1 之前，需要先完成课程 0。示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 输出：false 解释：总共有 2 门课程，但课程 0 和课程 1 互为先修，形成环。提示：
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
prerequisites 中的课程对互不相同
解题分析
1. 抽象为有向图判环问题
每门课程可以视作图中的节点
每个先修关系
[a, b]可以视作一条有向边：b -> a题目实质：判断课程依赖图是否有环
关键结论：
图中存在环 → 不可能完成所有课程
图中无环 → 可以完成所有课程
2. 拓扑排序（BFS）解法
核心思路：
建立邻接表表示图
统计每个节点的入度（还有多少前置课程未学）
将入度为 0 的节点入队
BFS 遍历：
出队节点表示已经学完
对它的邻接节点，入度减 1
如果邻接节点入度变为 0，入队
最后判断是否所有节点都被处理
优点：
时间复杂度 O(V + E)
空间复杂度 O(V + E)
思路清晰，易于理解
3. C 语言实现
#include <stdlib.h> #include <stdbool.h> bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize) { // 邻接表 int** graph = (int**)malloc(sizeof(int*) * numCourses); int* graphColSize = (int*)calloc(numCourses, sizeof(int)); // 入度数组 int* indegree = (int*)calloc(numCourses, sizeof(int)); // 初始化邻接表空间 for (int i = 0; i < numCourses; i++) { graph[i] = (int*)malloc(sizeof(int) * prerequisitesSize); } // 建图 + 统计入度 for (int i = 0; i < prerequisitesSize; i++) { int a = prerequisites[i][0]; int b = prerequisites[i][1]; graph[b][graphColSize[b]++] = a; indegree[a]++; } // 队列 int* queue = (int*)malloc(sizeof(int) * numCourses); int front = 0, rear = 0; // 入度为 0 的课程入队 for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) { queue[rear++] = i; } } int count = 0; // BFS 遍历 while (front < rear) { int cur = queue[front++]; count++; for (int i = 0; i < graphColSize[cur]; i++) { int next = graph[cur][i]; indegree[next]--; if (indegree[next] == 0) { queue[rear++] = next; } } } // 判断是否所有课程都能完成 return count == numCourses; }4. 复杂度分析
| 项目 | 复杂度 |
|---|---|
| 时间 | O(V + E) |
| 空间 | O(V + E) |
V = 课程数
numCoursesE = 先修课程对数
prerequisitesSize
5. 拓展思路
DFS 判环法
对每个节点进行 DFS，标记访问状态：
0：未访问
1：访问中（递归栈）
2：已访问完成
如果 DFS 过程中遇到状态为 1 的节点 → 存在环 → 返回 false
实际应用场景
大学课程规划
软件包依赖关系解析
项目任务调度
6. 总结
本题核心是判断有向图是否有环
BFS（拓扑排序）和 DFS（递归判环）都是高频面试解法
面试中可以结合题目要求灵活选择
拓扑排序是图论入门的重要算法，理解它对于课程表、任务调度、依赖关系等问题都非常有帮助。