【LeetCode】210. 课程表 II—

【LeetCode】210. 课程表 II——拓扑排序

题目链接：210. 课程表 II

题目描述：
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组。
``
在这里插入图片描述
数据范围：

题解：从题目描述来看，很容易就知道是拓扑排序问题了，问题在于如何存图，如何解答，存图方式比较多，邻接表、邻接矩阵，解方面：遍历、搜索、以及队列都能完成该题的解答，实现方面很多时候还是会依赖一些语言特性，比如java、c++中有队列，可以将度为0的点放进队列中，每次出队一个去边，而在golang中数据结构支持相对匮乏，因此可以采用遍历或者搜索方式完成。

本次采用遍历方式，首先记录每个节点的入度，以及边的关系，遍历节点，每次选出一个度为0且未被选过的节点，然后去掉与这个节点相连的边，一共会执行numCourses次操作，当操作完后发现记录的答案中没有numCourses个节点，那么表示不能完成拓扑排序动作。

直接遍历：

func findOrder(numCourses int, prerequisites [][]int) []int {edges := make([][]int, numCourses, numCourses) // 存储边的关系for i := range edges {edges[i] = make([]int, numCourses, numCourses)}in := make([]int, numCourses, numCourses) // 记录入度for i := 0; i < len(prerequisites); i++ {a := prerequisites[i][0]b := prerequisites[i][1]edges[b][a] = 1 // 表示a指向b的边in[a]++}res := make([]int, 0, numCourses)// 遍历入度为0的点，然后去掉这些点相连的边for i := 0; i < numCourses; i++ { //共numCourses次操作，k := 0 // 记录当前寻找的入度为0的点for j := 0; j < numCourses; j++ { // 找一个度为0且未被遍历过的点if in[j] == 0 {res = append(res, j)in[j] = -1 // 记得标记为-1，已经找过的路径不再往下寻找k = jbreak}}for j := 0; j < numCourses; j++ {if edges[k][j] == 1 {edges[k][j] = -1 // 断开这条边in[j]-- //j点的入度-1}}}if len(res) != numCourses {return []int{}}return res
}

上述方式采用邻接矩阵方式来存储图，并且通过遍历方式来计算答案，虽然总共只操作n次，但每次都需要找寻度为0的节点，断开与该节点相连的边，这样会有很多次无效的遍历，浪费时间，因此，我们可以进行进一步的优化。

队列方式：

func findOrder(numCourses int, prerequisites [][]int) []int {edges := make([][]int, numCourses, numCourses) // 存储边的关系for i := range edges {edges[i] = make([]int, numCourses, numCourses)}in := make([]int, numCourses, numCourses) // 记录入度for i := 0; i < len(prerequisites); i++ {a := prerequisites[i][0]b := prerequisites[i][1]edges[b][a] = 1 // 表示a指向b的边in[a]++}queue := make([]int, 0, numCourses)for i := 0; i < numCourses; i++ {if in[i] == 0 {queue = append(queue, i)in[i] = -1}}res := make([]int, 0, numCourses) // 记录答案// 模拟一下队列for len(queue) > 0 {cur := queue[0]res = append(res, cur)queue = queue[1:] // 相当于除去这个元素// 从cur这个节点开始出发，断边for i := 0; i < numCourses; i++ {if edges[cur][i] == 1 { // 如果有边，则减少入度in[i]--edges[cur][i] = -1 // 断开这条边// 如果没有依赖边了，加入队列中if in[i] == 0 {queue = append(queue, i)}}}}if len(res) != numCourses {return []int{}}return res
}

当然，前面的存储我们都采用了邻接矩阵方式存储，找边的时候只能一个个遍历去寻找，不妨换一种思路，采用邻接表方式来存储，优化一下代码：

func findOrder(numCourses int, prerequisites [][]int) []int {edges := make([][]int, numCourses) // 存储边的关系fmt.Println(len(edges))in := make([]int, numCourses, numCourses) // 记录入度for i := 0; i < len(prerequisites); i++ {u := prerequisites[i][0]v := prerequisites[i][1]edges[v] = append(edges[v], u) // 记录v点指向的各个节点in[u]++}queue := make([]int, 0, numCourses)for i := 0; i < numCourses; i++ {if in[i] == 0 {queue = append(queue, i)}}res := make([]int, 0, numCourses) // 记录答案// 模拟一下队列for len(queue) > 0 {cur := queue[0]res = append(res, cur)queue = queue[1:]// 从cur这个节点开始出发，断边for _, v := range edges[cur] {in[v]--if in[v] == 0 {queue = append(queue, v)}}}if len(res) != numCourses {return []int{}}return res
}