难度中等标签图论、拓扑排序、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)存图 入度数组 队列 结果数组总结这类课程安排问题本质上是有向图的拓扑排序。面试中可熟练使用BFSKahn 算法或DFS 拓扑排序带环检测。对于多解情况返回任意合法拓扑序即可。