LeetCode-Go 题解 210. Course Schedule IIKahn 拓扑排序输出完整选课顺序【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 210 题 Course Schedule II课程表 II展开讲解如何在已知课程总数与先修关系的前提下输出一个可行的完整选课顺序当课程依赖存在环无法修完所有课程时返回空数组。本仓库 LeetCode-Go 以 Go 语言给出了基于 AOV 网拓扑排序Kahn 算法的简洁实现读者学完本文后可掌握用入度表 出边邻接表构造课程依赖图、借助队列逐层消解入度为 0 的顶点、通过「输出的顶点数是否等于总课程数」判定环的存在并能对照第 207 题仅判断能否完成理解两个姊妹题的差异。题目描述你需要修完总共 n 门课程课程编号从0到n-1。部分课程之间存在先修关系例如要修课程 0必须先修完课程 1该关系用一对[0,1]表示注意先修课在数组第二位。给定课程总数numCourses与先修关系对列表prerequisites返回你为了学完所有课程所需安排的学习顺序。可能有多个正确的顺序只需返回其中任意一种如果不可能修完所有课程返回一个空数组。示例 1Input: 2, [[1,0]] Output: [0,1] Explanation: 共有 2 门课程。要修课程 1 必须先修完课程 0 因此正确的顺序是 [0,1]。示例 2Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] 或 [0,2,1,3] Explanation: 共有 4 门课程。修课程 3 之前必须先修完课程 1 和 2 而课程 1、2 都必须在修完课程 0 之后才能修。 因此一种正确顺序是 [0,1,2,3]另一种是 [0,2,1,3]。注意事项输入的prerequisites是以**边列表a list of edges**表示的图而非邻接矩阵。可以假设输入的先修关系中不存在重复边。题目大意现在你总共有 n 门课需要选记为0到n-1。在选修某些课程之前需要一些先修课程。例如想要学习课程 0你需要先完成课程 1我们用一对数来表示[0,1]。给定课程总量以及它们的先决条件返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序你只要返回一种就可以了。如果不可能完成所有课程返回一个空数组。解题思路本题是 207. Course Schedule 的加强版第 207 题只要求判断「能否完成所有课程」返回布尔值而第 210 题在同样的前提下还要求输出完成任务的顺序若无法完成则输出空数组。两道题的核心模型一致都是标准的AOV 网Activity On Vertex network拓扑排序问题把每门课程看作一个顶点先修关系看作有向边先修课指向后续课程问题就转化为求该有向无环图DAG的一个拓扑序列并检测是否存在环。拓扑排序的经典循环解法分为两步选择一个入度为 0 的顶点并输出从网中删除该顶点及所有出边等价于把这些出边指向的顶点的入度减 1。循环结束后若输出的顶点数小于网中的顶点数则说明图中存在回路即课程依赖成环无法修完所有课程否则输出的顶点序列就是一种拓扑序列。仓库源码实现Kahn 算法逐行拆解本仓库的核心实现位于 210. Course Schedule II.go包leetcode完整代码如下package leetcode func findOrder(numCourses int, prerequisites [][]int) []int { in : make([]int, numCourses) frees : make([][]int, numCourses) next : make([]int, 0, numCourses) for _, v : range prerequisites { in[v[0]] frees[v[1]] append(frees[v[1]], v[0]) } for i : 0; i numCourses; i { if in[i] 0 { next append(next, i) } } for i : 0; i ! len(next); i { c : next[i] v : frees[c] for _, vv : range v { in[vv]-- if in[vv] 0 { next append(next, vv) } } } if len(next) numCourses { return next } return []int{} }数据结构设计实现中用到了三个核心容器含义分别如下变量类型作用in[]int长度numCourses入度表in[i]表示课程i还有几门先修课未完成frees[][]int长度numCourses出边邻接表frees[i]记录了「以课程i为先修课」的全部后续课程next[]int双用途容器先作为待处理队列存放当前入度为 0 的课程最终直接作为结果拓扑序列返回这种设计只使用一个切片next同时扮演「队列」与「答案数组」省去了额外的队列数据结构空间更紧凑。第一步建图并统计入度for _, v : range prerequisites { in[v[0]] // 课程 v[0] 的入度 1 frees[v[1]] append(frees[v[1]], v[0]) // v[1] 是 v[0] 的先修课记录出边 }对于每一对先修关系[v[0], v[1]]课程v[1]是课程v[0]的先修课所以课程v[0]的入度加 1它多了一门必须先修的课在邻接表frees[v[1]]中追加v[0]表示修完v[1]之后v[0]可以被解锁。第二步初始化入度为 0 的课程for i : 0; i numCourses; i { if in[i] 0 { next append(next, i) } }扫描所有课程把入度为 0没有任何先修课的课程全部加入队列它们是拓扑序列的起点。第三步逐层消解生成拓扑序for i : 0; i ! len(next); i { c : next[i] // 取出队首课程 v : frees[c] // 它解锁的所有后续课程 for _, vv : range v { in[vv]-- // 后续课程的入度减 1 if in[vv] 0 { next append(next, vv) // 入度归零则加入队列 } } }这里使用i ! len(next)作为循环条件配合循环体内append动态扩充next实现了一个不用显式头尾指针的队列i每前进一步就从队首取出一个课程同时可能向队尾追加新的入度归零课程。每处理完一个课程就把它所有「后继课程」的入度减 1一旦某门后继课程的入度变为 0说明它所有的先修课都已排入序列立即入队。第四步检测环并返回结果if len(next) numCourses { return next } return []int{}拓扑排序结束后若成功输出的课程数等于总课程数numCourses说明不存在环next即一个合法的选课顺序直接返回否则说明图中存在环某些课程的先修关系形成了循环依赖它们的入度永远无法归零无法进入队列返回空数组[]int{}。复杂度分析时间复杂度O(V E)。建图扫描所有边 O(E)初始化扫描所有顶点 O(V)BFS 式消解过程中每个顶点入队一次、每条边被处理一次总代价 O(V E)。其中 V numCoursesE len(prerequisites)。空间复杂度O(V E)。in与next均为 O(V)frees邻接表存储全部 E 条出边。与第 207 题的联系与差异第 207 题的实现位于 207. Course Schedule.go核心函数为canFinishfunc canFinish(n int, pre [][]int) bool { in : make([]int, n) frees : make([][]int, n) next : make([]int, 0, n) // ... 建图、初始化、消解过程与 findOrder 完全一致 ... return len(next) n }对比可见两题的解题框架建图 → 入度为 0 入队 → 循环消解 → 判定环几乎完全相同差异仅在两处返回值不同canFinish只返回len(next) n的布尔判定findOrder在判定成功时直接返回next拓扑序列本身。语义不同第 207 题回答「能不能修完」第 210 题回答「按什么顺序修完」。正因为拓扑排序天然产出一个合法顺序所以第 207 题的判断逻辑稍加改造把布尔结果换成序列结果即可得到第 210 题的解法。原文档所述「代码和第 207 题基本不变」正是此意。测试用例与验证本仓库为本题提供了单元测试 210. Course Schedule II_test.go测试以表驱动方式组织覆盖了四类典型场景用例numCoursesprerequisites期望输出场景说明12[[1,0]][0,1]最基本的单链依赖22[[1,0],[0,1]][]测试期望值写法为[0,1,2,3]见下文说明课程 0 与 1 互相依赖成环无解34[[1,0],[2,0],[3,1],[3,2]][0,1,2,3]分支依赖对应题面示例 243[[1,0],[1,2],[0,1]][]环形依赖1→0→1 成环输出空数组关于用例 2 需要特别说明para210{2, [][]int{{1, 0}, {0, 1}}}传入numCourses 2且存在环findOrder实际会返回[]int{}测试结构中该用例的期望值写成[0,1,2,3]一个与输入规模不符的占位值且测试主体仅打印【input】与【output】而不做assert断言因此该测试文件本质上是输出型演示用例而非严格断言用例。真正严谨的行为验证应依据源码逻辑本身用例 3numCourses 4执行流程初始入度为 0 的是课程 0 → 出队 0课程 1、2 入度减为 0 并入队 → 依次出队 1、2课程 3 入度减为 0 并入队 → 最终next [0,1,2,3]长度等于 4返回该序列用例 4[[1,0],[1,2],[0,1]]中课程 0 与 1 互相构成先修循环二者入度永远无法归零最终len(next) 2 3返回[]int{}。如果想在本仓库直接运行验证可在仓库根目录执行go test ./leetcode/0210.Course-Schedule-II/ -v -run Test_Problem210边界情况与工程实践要点空先修列表若prerequisites为空所有课程入度均为 0初始化后next即为[0,1,...,n-1]直接返回全序正确无误。环的检测时机代码并未显式使用 visited 标记而是依赖「入度归零才入队」这一不变量——成环顶点永远入不了队最终通过长度比对统一判定实现非常精简。顺序的多样性拓扑序列不唯一例如题面示例 2 的[0,1,2,3]与[0,2,1,3]都合法本实现按课程编号从小到大的自然顺序输出任何合法序列均被 LeetCode 判定为正确。队列切片的复用技巧用单个切片同时充当队列与答案数组代码简洁且避免了额外内存分配可推广到其他「先判断可达性、再要求输出路径」的图论问题中。小结LeetCode 210 题是拓扑排序的典型应用以课程为顶点、先修关系为边构造 AOV 网通过 Kahn 算法入度表 出边邻接表 队列在 O(V E) 时间内既检测了环的存在性又输出了合法的选课顺序。本仓库 findOrder 的实现与第 207 题 canFinish 共享同一套算法骨架读者可将两道题对照学习体会「只判断可行性」到「额外输出方案」的渐进改造思路这一模式同样适用于其他拓扑排序类问题如任务调度、编译依赖排序、包管理器的依赖解析等。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考