拓扑排序算法

拓扑排序概念

一个较大的工程往往会被划分成许多子工程，在整个工程中，这些子工程必须在它有关的子工程完成后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始，为了形象的反应出整个工程中各个子工程之间的先后关系，可以用一个邮箱图来表示，图中的顶点表示活动，图中的有向边代表活动的先后关系，通常，我们把这种顶点表示活动，边表示活动时间先后关系的又想吐陈祚顶点的活动网，简称AOV网。
而在日常生活中，我们经常可以遇到的就是学生选课系统，如想学习数据结构，就必须先学习离散数学和算法语言。
而在Android的世界中，拓扑排序常用的地方也是在优化app启动的过程中，将各个初始化任务抽象成activity，按重要程度和先后顺序进行拓扑排序，这样就可以异步的进行app的初始化，有效的缩短应用初始化时间。

基本概念

入度

设有向图中有一节点node，其入度即为当前所有其他节点出发，终点为node的边的树木，也就是所有指向v的有向边的数目。

出度

设邮箱图中有一节点node，其出度即为当前所有起点为node，指向其他节点的有向边数目，也就是所有由node发出的边的数目。

逻辑算法

在了解了入度和出度的概念之后，再根据拓扑排序的定义。可以得出结论：要完成拓扑排序，每次都应当从入度为0的节点开始遍历。
而此时也有深度优先和广度优先遍历的算法，

  1. 定义个int[] inDegree保存每一个节点的入度
  2. 对于图的每一个节点的子节点，讲其入度加1
  3. 选取入度为0的节点开始遍历，输出该节点
  4. 遍历的每个节点，更新其子节点的入度，将子节点的入度-1
  5. 重复步骤3，直到所有节点结束

java代码：

public class TopologicalSort {
    public List<Integer> topologicalSort(int n, int[][] adjacencyList) {
        List<Integer> topoRes = new ArrayList<>();
        int[] inDegree = new int[n];
        for (int[] parent : adjacencyList) {
            for (int child : parent) {
                inDegree[child]++;
            }
        }
        
        Deque<Integer> deque = new ArrayDeque<>();
        
        // start from nodes whose indegree are 0
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) deque.offer(i);
        }
        
        while (!deque.isEmpty()) {
            int curr = deque.poll();
            topoRes.add(curr);
            for (int child : adjacencyList[curr]) {
                inDegree[child]--;
                if (inDegree[child] == 0) {
                    deque.offer(child);
                }
            }
        }
    
        return topoRes.size() == n ? topoRes : new ArrayList<>();
    }
}
--> return <--