LeetCode 210. 课程表 II思路拓扑排序。若图中有环则无法完成所有课程返回空数组。解法一BFSKahn 算法推荐核心统计入度入度为 0 的入队出队时把邻居入度减 1减到 0 就入队。classSolution{publicint[]findOrder(intnumCourses,int[][]prerequisites){// 建图ListListIntegergraphnewArrayList();for(inti0;inumCourses;i){graph.add(newArrayList());}int[]indegreenewint[numCourses];for(int[]p:prerequisites){// p[1] - p[0]即先修 p[1] 才能修 p[0]graph.get(p[1]).add(p[0]);indegree[p[0]];}// 入度为 0 的课程入队DequeIntegerqueuenewArrayDeque();for(inti0;inumCourses;i){if(indegree[i]0)queue.offer(i);}int[]resultnewint[numCourses];intidx0;while(!queue.isEmpty()){intcurqueue.poll();result[idx]cur;for(intnext:graph.get(cur)){if(--indegree[next]0){queue.offer(next);}}}// 若没能修完所有课程说明有环returnidxnumCourses?result:newint[0];}}解法二DFS三色标记核心0 未访问1 访问中2 已完成。遇到 1 说明有环。后序遍历的逆序即为拓扑序。classSolution{privateListListIntegergraph;privateint[]state;// 0 未访问, 1 访问中, 2 已完成privateint[]result;privateintidx;privatebooleanhasCycle;publicint[]findOrder(intnumCourses,int[][]prerequisites){graphnewArrayList();for(inti0;inumCourses;i){graph.add(newArrayList());}for(int[]p:prerequisites){graph.get(p[1]).add(p[0]);}statenewint[numCourses];resultnewint[numCourses];idxnumCourses-1;// 从后往前填因为后序是逆序for(inti0;inumCourses;i){if(state[i]0){dfs(i);}if(hasCycle)returnnewint[0];}returnresult;}privatevoiddfs(intu){state[u]1;for(intv:graph.get(u)){if(state[v]1){// 遇到正在访问中的节点 - 有环hasCycletrue;return;}if(state[v]0){dfs(v);if(hasCycle)return;}}state[u]2;result[idx--]u;// 后序位置记录}}复杂度分析· 时间O(V E)V 为课程数E 为先修关系数每个节点和边都只处理一次· 空间O(V E)邻接表 入度/状态数组关键点边的方向prerequisites[i] [a, b] 表示 b - a别建反了判断有环BFS 中「出队节点数 numCourses」DFS 中「遇到访问中节点」DFS 逆序递归返回时才记录节点最终结果是拓扑序的反向可以用栈或倒序数组多解拓扑序不唯一题目接受任意合法顺序通常按序号从小到大的入队顺序即可通过两种方法任选其一即可BFS 更直观、更推荐。