企业官网建设流程全解析

LeetCode-Go 题解 210. Course Schedule II：Kahn 拓扑排序输出完整选课顺序

【免费下载链接】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，返回你为了学完所有课程所需安排的学习顺序。可能有多个正确的顺序，只需返回其中任意一种；如果不可能修完所有课程，返回一个空数组。

示例 1：

Input: 2, [[1,0]] Output: [0,1] Explanation: 共有 2 门课程。要修课程 1 必须先修完课程 0， 因此正确的顺序是 [0,1]。

示例 2：

Input: 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]。

注意事项：

1. 输入的prerequisites是以**边列表（a list of edges）**表示的图，而非邻接矩阵。
2. 可以假设输入的先修关系中不存在重复边。

题目大意

现在你总共有 n 门课需要选，记为0到n-1。在选修某些课程之前需要一些先修课程。例如，想要学习课程 0，你需要先完成课程 1，我们用一对数来表示：[0,1]。给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

解题思路

本题是 207. Course Schedule 的加强版：第 207 题只要求判断「能否完成所有课程」（返回布尔值），而第 210 题在同样的前提下还要求输出完成任务的顺序，若无法完成则输出空数组。

两道题的核心模型一致，都是标准的AOV 网（Activity On Vertex network）拓扑排序问题：把每门课程看作一个顶点，先修关系看作有向边（先修课指向后续课程），问题就转化为求该有向无环图（DAG）的一个拓扑序列，并检测是否存在环。

拓扑排序的经典循环解法分为两步：

1. 选择一个入度为 0 的顶点并输出；
2. 从网中删除该顶点及所有出边（等价于把这些出边指向的顶点的入度减 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{} }

数据结构设计

实现中用到了三个核心容器，含义分别如下：

这种设计只使用一个切片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 =numCourses，E =len(prerequisites)。
• 空间复杂度：O(V + E)。in与next均为 O(V)，frees邻接表存储全部 E 条出边。

与第 207 题的联系与差异

第 207 题的实现位于 207. Course Schedule.go，核心函数为canFinish：

func 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 入队 → 循环消解 → 判定环）几乎完全相同，差异仅在两处：

1. 返回值不同：canFinish只返回len(next) == n的布尔判定；findOrder在判定成功时直接返回next拓扑序列本身。
2. 语义不同：第 207 题回答「能不能修完」，第 210 题回答「按什么顺序修完」。正因为拓扑排序天然产出一个合法顺序，所以第 207 题的判断逻辑稍加改造（把布尔结果换成序列结果）即可得到第 210 题的解法。原文档所述「代码和第 207 题基本不变」正是此意。

测试用例与验证

本仓库为本题提供了单元测试 210. Course Schedule II_test.go，测试以表驱动方式组织，覆盖了四类典型场景：

关于用例 2 需要特别说明：para210{2, [][]int{{1, 0}, {0, 1}}}传入numCourses = 2且存在环，findOrder实际会返回[]int{}；测试结构中该用例的期望值写成[0,1,2,3]（一个与输入规模不符的占位值），且测试主体仅打印【input】与【output】而不做assert断言，因此该测试文件本质上是输出型演示用例而非严格断言用例。真正严谨的行为验证应依据源码逻辑本身：

• 用例 3（numCourses = 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