拓扑排序Golang实现
原创
以前一直不太懂拓扑排序的实现，今天在知乎上面看到一篇文章讲拓扑排序，讲的特别清楚，一下子明朗了。链接如下：https://zhuanlan.zhihu.com/p/135094687。
其实就是有向无环图的广度优先搜索，寻找一条可行的道路，且每个节点的先决条件有特定的几个。这样去理解拓扑排序就很好理解了。基于拓扑排序的题目有最典型的207题：课程表1， 210题：课程表2。这两道题都是很典型的使用广度优先搜索来实现拓扑排序。思路是：通过将先决条件作为入度数组，以及记录自身为另外节点的先决条件的数组（也就是出度数组），将入度为0的元素加入到队列，然后遍历出度数组，将子元素的入度-1，再将入度为0的元素加入到队列中去。1136题并行课程也是一道拓扑排序的题目：思路是一个学期只能学习一轮，这个题目单独拿出来讲是因为我觉得这道题类似二叉树的层次遍历，每次出队的时候跟课程表系列的题目不同，只需要将一轮队列中的元素个数遍历完才能增加一次计数，然后才能进行下一轮遍历队列。这样通过判断几轮进行下来的课程数是否是题目要求的数量进行对比即可知道是否有可行的拓扑排序。以下是该题目的解，在此记录一下：
func minimumSemesters(n int, relations [][]int) int {
inEdge, outEdge := make([]int, n + 1), make([][]int, n + 1)
term := 0
queue := make([]int, 0)
cntCourse := 0
for _, relation := range relations {
outEdge[relation[0]] = append(outEdge[relation[0]], relation[1])
inEdge[relation[1]]++
}
for i := 1; i < n + 1; i++ {
if inEdge[i] == 0 {
queue = append(queue, i)
}
}
for len(queue) != 0 {
term++
n := len(queue)
for i := 0; i < n; i++ {
poll := queue[0]
queue = queue[1:]
cntCourse++
for _, next := range outEdge[poll] {
inEdge[next]--
if inEdge[next] == 0 {
queue = append(queue, next)
}
}
}
}
if cntCourse != n {
return -1
}
return term
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读