LeetCode 210 课程表 II | 拓扑排序详解（C语言实现）
难度：中等
标签：图论、拓扑排序、BFS、DFS
题目描述
现在你总共有numCourses门课程需要选，记为0到numCourses - 1。给你一个数组prerequisites，其中prerequisites[i] = [ai, bi]，表示在选修课程ai前必须先完成课程bi。
请你返回一个可行的课程学习顺序。如果不存在这样的顺序（存在环），返回空数组。
示例：
输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 输出: [0,2,1,3] 解释: 学习课程 3 需要先学课程 1 和课程 2，而课程 1 和 2 都要在课程 0 后。解题思路
这题是经典的拓扑排序问题：
建图：将课程和先修关系建成有向图。
统计入度：每门课程的入度表示它的先修课程数量。
BFS 遍历：
将入度为 0 的课程加入队列。
每次出队一个课程，加入结果数组。
遍历其邻接点，入度减 1，如果入度为 0，加入队列。
判断环：
BFS 后，如果结果数组长度 != numCourses，则说明存在环，返回空数组。
返回拓扑序：
BFS 遍历完，结果数组即为合法的课程顺序。
这种方法叫做Kahn 算法，时间复杂度为 O(V + E)。
C语言代码实现（BFS）
#include <stdio.h> #include <stdlib.h> /** * Note: The returned array must be malloced, assume caller calls free(). */ int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize) { // 邻接表 int** graph = (int**)malloc(sizeof(int*) * numCourses); int* graphColSize = (int*)calloc(numCourses, sizeof(int)); for (int i = 0; i < numCourses; i++) { graph[i] = (int*)malloc(sizeof(int) * prerequisitesSize); } // 入度数组 int* indegree = (int*)calloc(numCourses, sizeof(int)); // 建图 + 统计入度 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* res = (int*)malloc(sizeof(int) * numCourses); int count = 0; // BFS while (front < rear) { int cur = queue[front++]; res[count++] = cur; for (int i = 0; i < graphColSize[cur]; i++) { int next = graph[cur][i]; indegree[next]--; if (indegree[next] == 0) { queue[rear++] = next; } } } if (count != numCourses) { *returnSize = 0; return (int*)malloc(0); } *returnSize = numCourses; return res; }思路分析
建图
将先修关系[ai, bi]转化为有向边bi -> ai。入度统计
入度数组indegree[i]表示课程i还有多少先修课程未完成。BFS 拓扑排序
队列存入度为 0 的课程。
每次出队，加入结果数组。
遍历出队课程的邻接课程，将入度减 1，若为 0 则入队。
检测环
如果 BFS 后结果数组长度不等于课程总数，说明图中存在环，返回空数组。
时间复杂度与空间复杂度
时间复杂度：O(V + E)
V：课程数量
E：先修关系数量
空间复杂度：O(V + E)
存图 + 入度数组 + 队列 + 结果数组
总结
这类课程安排问题本质上是有向图的拓扑排序。
面试中可熟练使用BFS（Kahn 算法）或DFS 拓扑排序（带环检测）。
对于多解情况，返回任意合法拓扑序即可。