LeetCode 210 课程表 II

Ciel Yang 收录于类别练习 OJ解题报告

2020-05-17 2020-05-17 约 1290 字预计阅读 3 分钟

本题是一道标准的拓扑排序试题，非常适合作为例题学习拓扑排序的相关知识。

题目描述

原题链接如下： LeetCode 210 课程表 II

题目大意

选课的依赖关系可以抽象为有向图，图的边 u -> v 表示必须先修完课程 u 才能选修课程 v，这样选课顺序就是这个图的拓扑排序结果。当然，前提条件是图必须时 DAG（有向无环图）。

输入与输出

输入为两个课程直接的依赖关系，使用长度为 2 的数组表示，[0, 1] 表示在选修编号为 0 的课程之前，必须先修完 1 号课程。

1
2
3
4
5
6
7
Input 1:
numOfCourses = 2
prerequisites = [[1,0]]

Input 2:
numOfCourses = 2
prerequisites = [[1,0],[2,0],[3,1],[3,2]]

一组输入可能会产生多种不同的合法输出，任选其一即可。

1
2
3
4
5
Output 1:
[0,1]

Output 2:
[0,1,2,3] or [0,2,1,3]

解题思路

使用标准的拓扑排序即可，下面主要是对两种拓扑排序算法的内容进行简述。另外，为了方便计算，本题中使用邻接表的形式存储图的相关信息。

Kahn 算法

Kahn 算法的核心思路包含贪心方法：

图的拓扑排序的起点必定是入度为 0 的点，而这些点无所谓排序顺序，可以随意放入结果序列中
删除掉起点以及相关的边后产生新的图再使用步骤 1，仍可以找出新图的起点

不断断定和删除起点，就能够不断得到可靠的结果序列。每次找出一批起点，然后再找出下一层起点，其结构大体就是 BFS 算法的框架。最后，得到的结果序列如果长度不等于图的顶点，就表示原图有环。

注意：邻接表不方便查询入度为 0 的点有哪些，要额外再维护一个入度表方便查询。当然，每次删除起点后也要相应更新入度表对应项，反而无需修改邻接表内容。

DFS 算法

DFS 算法类似 Kahn 算法的逆向思路，即不从起点开始构建结果序列，而是从终点开始构建，具体算法步骤如下：

从任意点开始作为根节点，可以从图生成一棵树，把它的叶子节点存入结果序列
对剩余的点可以使用步骤 1 的方法找到叶子节点，放入结果序列
遍历时，不断删除找到的叶子节点，可以得到新图，而新图也必定会有新的终点

当然，删除叶子节点的方法可以通过标明节点的访问状态来实现，删除就是把叶子节点标记为 visited。但是，如果用这种方法实际上会在环中陷入无限循环（即无法判断环是否存在）。所以我们必须拓展访问状态:

not visited：节点的初始状态，未曾有任何操作
visiting：遍历进行时起始节点的状态
visited：已被删除的叶子节点

因为，实际遍历是递归的，我们会把遍历路径上所有已经遍历过的点都标记为 visiting，然后只要发现新的子节点是 visiting 状态就说明必定有环。

注意：删除叶子节点时会把节点状态置为 visited，递归的形式会保证路径上的节点由叶子到根被一层层置为 visited。

代码

Kahn 算法：

 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
import java.util.LinkedList
import java.util.Queue

class Solution {
    fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
        val inDegreeCounter = IntArray(numCourses)
        val adjList = Array(numCourses) { ArrayList<Int>() }
        val cache: Queue<Int> = LinkedList()
        val re = ArrayList<Int>()
        // init inDegreeArray
        for (edge in prerequisites) {
            adjList[edge[1]].add(edge[0])
            inDegreeCounter[edge[0]]++
        }
        for (i in inDegreeCounter.indices) {
            if (inDegreeCounter[i] == 0) cache.offer(i)
        }
        while (cache.isNotEmpty()) {
            val node = cache.poll()
            re.add(node)
            for (dest in adjList[node]) {
                inDegreeCounter[dest]--
                if (inDegreeCounter[dest] == 0) cache.offer(dest)
            }
        }
        return if (re.size == numCourses) re.toIntArray() else IntArray(0)
    }
}

DFS 算法：

 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
class Solution {
    private lateinit var edges: Array<ArrayList<Int>>
    private val cache = ArrayList<Int>()
    private lateinit var states: Array<State>

    fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
        edges = Array(numCourses) { ArrayList<Int>() }
        states = Array(numCourses) { State.NOT_VISITED }
        for (arr in prerequisites) {
            edges[arr[1]].add(arr[0])
        }
        for (i in 0 until numCourses) {
            if (dfs(i)) return IntArray(0)
        }
        return cache.asReversed().toIntArray()
    }

    private fun dfs(node: Int): Boolean {
        if (states[node] == State.VISITED) return false
        if (states[node] == State.VISITING) return true
        states[node] = State.VISITING
        for (next in edges[node]) {
            if (dfs(next)) return true
        }
        states[node] = State.VISITED
        cache.add(node)
        return false
    }

    private enum class State {
        NOT_VISITED, VISITING, VISITED
    }
}

目录