207. 课程表 - 力扣（LeetCode）
思路
课程之间的依赖关系可以用图来表示
- 顶点：课程
- 边：有向的边，起点是前置课程，终点是后置课程
这种图叫做AOV（Activity On Vertex）网络，字面意思就是边代表了节点之间的活动的先后关系。
按照题意，这个图是无环的（课程不能循环依赖），也就是DAG图。DAG图其实就是一颗树，只不过根节点是一个虚拟根节点（可以有多个起始根节点，但外面可以用一个虚拟根节点作为他们的父节点）。
因此，可以用广度优先遍历（BFS）来求解。队列存放可以选的课程（入度为0），依次出队列（选课）。直到队列为空（没有课可以选了），看是否已经学完所有的课程
- 入度：指向自己的边的数量，入度为0表示自己没有前置课程，可以入队列
- 出度：指向别人的边。用一个数据结构记录每个节点的出度列表。当某个节点出队列时，更新本节点的出度列表里所有节点的入度（-1）
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| func canFinish(numCourses int, prerequisites [][]int) bool {
//保存各课程的入度 空间O(v)
indegree := make([]int, numCourses)
// 保存各课程的出度列表 空间O(e)
courseMp := make(map[int][]int)
//时间 O(e)
for _, pre := range(prerequisites) {
indegree[pre[0]]++
courseMp[pre[1]] = append(courseMp[pre[1]], pre[0])
}
var q []int
// 已经学习了的课程的计数
var num int
// 初始入度为0的课程加入队列
for course, depends := range(indegree) {
if depends == 0 {
q = append(q, course)
}
}
//循环直到队列为空 时间O(v)
for len(q) > 0 {
// 出队列
finished := q[0]
q = q[1:]
num++
// 更新入度数据结构(slice)
// 从出度课程列表中直接取受影响的课程
for _, course := range(courseMp[finished]) {
indegree[course]--
// 入度-1后若为0，则可以入队列
if indegree[course] == 0 {
q = append(q, course)
}
}
}
//是否学完
return num == numCourses
}
|
- 时间复杂度：O (v+e)
- 空间复杂度: O(v+e)
若需要省空间，不需要省时间，可以不使用courseMp存放出度数组，每次重新遍历prerequisites 获取出度数组。此时处理每个节点都需要重新遍历所有的边，因此：
- 时间复杂度：O (v*e+e)
- 空间复杂度: O(v)
参考资料
图文详解面试常考算法 —— 拓扑排序 - 知乎 (zhihu.com)
Course Schedule II - LeetCode