拓扑排序(选课)

拓扑排序

207. 课程表 - 力扣（LeetCode）

思路

课程之间的依赖关系可以用图来表示

• 顶点：课程
• 边：有向的边，起点是前置课程，终点是后置课程

这种图叫做 AOV（Activity On Vertex）网络，字面意思就是边代表了节点之间的活动的先后关系。

按照题意，这个图是无环的（课程不能循环依赖），也就是 DAG 图。DAG 图其实就是一颗树，只不过根节点是一个虚拟根节点（可以有多个起始根节点，但外面可以用一个虚拟根节点作为他们的父节点）。

因此，可以用广度优先遍历（BFS）来求解。队列存放可以选的课程（入度为 0），依次出队列（选课）。直到队列为空（没有课可以选了），看是否已经学完所有的课程

• 入度：指向自己的边的数量，入度为 0 表示自己没有前置课程，可以入队列
• 出度：指向别人的边。用一个数据结构记录每个节点的出度列表。当某个节点出队列时，更新本节点的出度列表里所有节点的入度（-1）

代码

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