拓扑排序

什么是拓扑排序呢， 具体可参考网上别人的总结https://www.jianshu.com/p/b59db381561a，我这里不赘述了。之所以想研究这个算法呢？记得以前学 java 的时候，很多工程的构建是基于 Ant 来构建的，后来又通过 maven 来构建，再后来学习 Android 的时候，Android 工程是通过 Gradle 来构建的，Gradle 构建过程中会有很多独立的 task 执行，这些 task 又有依赖关系，有的 task 必须在某个 task 执行之前执行，还有就是模块的依赖关系，当时就在想编译系统是怎么确定这些前后依赖顺序的，后来了解到拓扑排序算之后才恍然大悟，这不就是一个典型的拓扑排序实践案例么。
拓扑排序主要有2种实现方式，下面用 Kotlin 代码分别实现：

1. 拓扑排序-Kahn算法

class TopoGraph(val size: Int) {

    //图的临界矩阵定义好
    private val adj: Array<LinkedList<Int>> = Array(size) {
        LinkedList<Int>()
    }

    //定义图的边
    fun addEdge(s: Int, t: Int) {
        adj[s].add(t)
    }

    /**
     * 拓扑排序 - Kahn算法
     */
    fun topoSortByKahn() {
        var inDegreeArr = IntArray(size)
        //计算所有顶点的入度 inDegree
        for (i in adj.indices) {
            var list = adj[i]
            for (item in list) {
                inDegreeArr[item]++
            }
        }
        //保存所有入度为 0 的顶点
        val queue = LinkedList<Int>()
        //先找出所有 inDegree = 0 的顶点
        for (i in inDegreeArr.indices) {
            if (inDegreeArr[i] == 0) {
                queue.add((i))
            }
        }
        while (queue.isNotEmpty()) {
            //inDegree = 0 的顶点先出队列
            var i = queue.remove()
            print("-> ${i} ")
            for (item in adj[i]) {
                //所有该顶点能到的其他顶点的 inDegree - 1
                inDegreeArr[item]--
                if (inDegreeArr[item] == 0) {
                    //如果 inDegree = 0 则先入队，然后循环处理
                    queue.add(item)
                }
            }
        }       
    }
}

2. 拓扑排序-DFS算法

    /**
     * 拓扑排序 - DFS算法(深度优先遍历)
     */
    fun topoSortByDfs() {
        //逆邻接表
        var reverseAdjList = Array(size) {
            LinkedList<Int>()
        }
        //记录节点是否已经遍历
        var visited = BooleanArray(size) { false }
        for (i in adj.indices) {
            var list = adj[i]
            for (item in list) {
                reverseAdjList[item].add(i)
            }
        }
        for (i in 0 until size) {
            if (!visited[i])
                dfs(reverseAdjList, visited, i)
        }
    }

    //类似二叉树的后序遍历
    private fun dfs(reverseAdjList: Array<LinkedList<Int>>, visited: BooleanArray, vertex: Int) {
        if (vertex >= size || visited[vertex]) {
            return
        }
        visited[vertex] = true
        var list = reverseAdjList[vertex]
        for (v in list) {
            if (!visited[v])
                dfs(reverseAdjList, visited, v)
        }
        print("-> ${vertex} ")
    }