拓扑排序Golang实现

原创

dddyge

发布于 2022-10-19 15:09:54

80800

代码可运行

文章被收录于专栏：思考与总结思考与总结

运行总次数：0

代码可运行

以前一直不太懂拓扑排序的实现，今天在知乎上面看到一篇文章讲拓扑排序，讲的特别清楚，一下子明朗了。链接如下：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
}