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 20000 prerequisites.length 5000prerequisites[i].length 20 a_i, b_i numCoursesprerequisites 中的课程对互不相同解题分析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 先修课程对数prerequisitesSize5. 拓展思路DFS 判环法对每个节点进行 DFS标记访问状态0未访问1访问中递归栈2已访问完成如果 DFS 过程中遇到状态为 1 的节点 → 存在环 → 返回 false实际应用场景大学课程规划软件包依赖关系解析项目任务调度6. 总结本题核心是判断有向图是否有环BFS拓扑排序和 DFS递归判环都是高频面试解法面试中可以结合题目要求灵活选择拓扑排序是图论入门的重要算法理解它对于课程表、任务调度、依赖关系等问题都非常有帮助。