课程表
课程表题的本质不是排课，而是判断一个有向图里有没有环；没环就能学完，有环就一定学不完。
问题描述
LeetCode 207 - 课程表
你需要选n门课程，记为0到n-1。在选某些课程之前需要先选其他课程。例如，想要学习课程0，需要先完成课程1，表示为[0,1]。给定课程总数和先修课程列表，判断是否可能完成所有课程的学习。
输入: numCourses = 2, prerequisites = [[1,0]]
输出: true
说明: 总共2门课，学习课程1之前需要先学习课程0，可以完成
输入: numCourses = 2, prerequisites = [[1,0],[0,1]]
输出: false
说明: 存在循环依赖，无法完成
解题思路
- 环检测：判断有向图是否存在环
- 拓扑排序：使用Kahn算法或DFS
- 入度统计：Kahn算法统计入度
- 三色标记：DFS使用三色标记检测环
为什么拓扑排序能做
把一条依赖 [a, b] 看成：
b -> a意思是先学 b，再学 a。
如果这张有向图存在环，就说明有一组课程互相依赖，谁都没法先开始。
Kahn 算法的思路很直接：
- 先把所有入度为
0的课放进队列。 - 每学完一门课，就删掉它对后续课程的影响。
- 如果最后能删完所有点，说明无环；否则有环。
Go 代码
Go 实现
func canFinish(numCourses int, prerequisites [][]int) bool {
graph := make([][]int, numCourses)
inDegree := make([]int, numCourses)
for _, prereq := range prerequisites {
course, pre := prereq[0], prereq[1]
graph[pre] = append(graph[pre], course)
inDegree[course]++
}
queue := []int{}
for i := 0; i < numCourses; i++ {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
count := 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
count++
for _, neighbor := range graph[node] {
inDegree[neighbor]--
if inDegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
return count == numCourses
}易错点
课程表这题最容易错的是边方向和“入度代表谁依赖谁”。
[a, b]不是a -> b，而是b -> a。- 入度统计的是“还有多少前置课程没学”。
- 最后判断条件不是队列空没空，而是弹出的课程数是否等于总课程数。
- 这题可以用 Kahn，也可以用 DFS 判环，但不要把两套状态混着写。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V+E) | V是课程数，E是依赖关系数 |
| 空间复杂度 | O(V+E) | 图和队列 |