关于android:Android-启动优化二-拓扑排序的原理以及解题思路

Android 启动优化（一）– 有向无环图

Android 启动优化（二）– 拓扑排序的原理以及解题思路

Android 启动优化（三）– AnchorTask 应用阐明

Android 启动优化（四）- 手把手教你实现 AnchorTask

Android 启动优化（五）- AnchorTask 1.0.0 版本更新了

Android 启动优化（六）- 深刻了解布局优化

这几篇文章从 0 到 1，解说 DAG 有向无环图是怎么实现的，以及在 Android 启动优化的利用。

举荐理由：当初挺多文章一谈到启动优化，动不动就聊拓扑构造，这篇文章从数据结构到算法、到设计都给大家说分明了，开源我的项目也有十分强的借鉴意义。

春节之前，更新了一篇博客 Android 启动优化（一）– 有向无环图，反应还不错，明天，让咱们一起来看一下，怎么用代码实现有向无环图。

拓扑排序的英文名是 Topological sorting。

拓扑排序要解决的问题是给一个图的所有节点排序。有向无环图才有拓扑排序，非有向无环图没有。

换句话说，拓扑排序必须满足以下条件

图必须是一个无环有向图。序列必须满足的条件：

每个顶点呈现且只呈现一次。
若存在一条从顶点 A 到顶点 B 的门路，那么在序列中顶点 A 呈现在顶点 B 的后面。

咱们已 leetcode 下面的一道算法题目作为切入点进行解说。

leeocode 210: https://leetcode-cn.com/probl…

eg: 当初你总共有 n 门课须要选，记为 0 到 n-1。

在选修某些课程之前须要一些先修课程。例如，想要学习课程 0，你须要先实现课程 1，咱们用一个匹配来示意他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安顿的学习程序。

可能会有多个正确的程序，你只有返回一种就能够了。如果不可能实现所有课程，返回一个空数组。

示例 1

输出: 2, [[1,0]] 
输入: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你须要先实现课程 0。因而，正确的课程程序为 [0,1]。

示例 2

输出: 4, [[1,0],[2,0],[3,1],[3,2]]
输入: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先实现课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因而，一个正确的课程程序是 [0,1,2,3]。另一个正确的排序是 [0,2,1,3]。

这道题，很显著，看起来能够有有向无环图的解法来解决

咱们首先引入有向图形容依赖关系

示例：假如 n = 6，先决条件表：[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4] ]

0, 1, 2 没有先修课，能够间接选。其余的，都要先修 2 门课
咱们用有向图形容这种依赖关系 (做事的先后关系)：

在有向图中，咱们晓得，有入度和出度概念：

如果存在一条有向边 A –> B，则这条边给 A 减少了 1 个出度，给 B 减少了 1 个入度。所以顶点 0、1、2 的入度为 0。顶点 3、4、5 的入度为 2

咱们关怀课程的入度 —— 该值要被减，要被监控
咱们关怀课程之间的依赖关系 —— 选这门课会减小哪些课的入度
因而咱们须要适合的数据结构，去存储这些关系, 这个能够通过哈希表

保护一个 queue，外面都是入度为 0 的课程
抉择一门课，就让它入列，同时 查看哈希表，看它对应哪些后续课
将这些后续课的入度 – 1，如果有减至 0 的，就将它推入 queue
不再有新的入度 0 的课入列时，此时 queue 为空，退出循环

    private  class Solution {public int[] findOrder(int num, int[][] prerequisites) {// 计算所有节点的入度，这里用数组代表哈希表，key 是 index，value 是 inDegree[index]. 理论开发当中，用 HashMap 比拟灵便
            int[] inDegree = new int[num];
            for (int[] array : prerequisites) {inDegree[array[0]]++;
            }

            // 找出所有入度为 0 的点，退出到队列当中
            Queue<Integer> queue = new ArrayDeque<>();
            for (int i = 0; i < inDegree.length; i++) {if (inDegree[i] == 0) {queue.add(i);
                }
            }
            
            ArrayList<Integer> result = new ArrayList<>();
            while (!queue.isEmpty()) {Integer key = queue.poll();
                result.add(key);
                // 遍历所有课程
                for (int[] p : prerequisites) {
                    // 改课程依赖于以后课程 key
                    if (key == p[1]) {
                        // 入度减一
                        inDegree[p[0]]--;
                        if (inDegree[p[0]] == 0) {queue.offer(p[0]); // 退出到队列当中
                        }
                    }
                }
            }

            // 数量不相等，阐明存在环
            if (result.size() != num) {return new int[0];
            }

            int[] array = new int[num];
            int index = 0;
            for (int i : result) {array[index++] = i;

            }

            return array;
        }
    }

对图执行深度优先搜寻。
在执行深度优先搜寻时，若某个顶点不能继续前进，即顶点的出度为 0，则将此顶点入栈。
最初失去栈中程序的逆序即为拓扑排序程序。

// 办法 2：邻接矩阵 + DFS   因为用的数组，每次都要遍历，效率比拟低
    public int[] findOrder(int numCourses, int[][] prerequisites) {if (numCourses == 0) return new int[0];
        // 建设邻接矩阵
        int[][] graph = new int[numCourses][numCourses];
        for (int[] p : prerequisites) {graph[p[1]][p[0]] = 1;
        }
        // 记录拜访状态的数组，拜访过了标记 -1，正在拜访标记 1，还未拜访标记 0
        int[] status = new int[numCourses];
        Stack<Integer> stack = new Stack<>();  // 用栈保留拜访序列
        for (int i = 0; i < numCourses; i++) {if (!dfs(graph, status, i, stack)) return new int[0]; // 只有存在环就返回
        }
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {res[i] = stack.pop();}
        return res;
    }

    private boolean dfs(int[][] graph, int[] status, int i, Stack<Integer> stack) {if (status[i] == 1) return false; // 以后节点在此次 dfs 中正在拜访，阐明存在环
        if (status[i] == -1) return true;

        status[i] = 1;
        for (int j = 0; j < graph.length; j++) {
            // dfs 拜访以后课程的后续课程，看是否存在环
            if (graph[i][j] == 1 && !dfs(graph, status, j, stack)) return false;
        }
        status[i] = -1;  // 标记为已拜访
        stack.push(i);
        return true;
    }

这篇博客从实战的角度登程，介绍了有向无环图的两种解法，入度表法和 DFS 法。其中，入度表法很重要，必须把握。下一篇，咱们将从我的项目实战的角度来解说，怎么搭建一个有向无环图的通用框架，敬请期待。

AnchorTask 源码曾经更新到 github，AnchorTask，下一篇，将输入 AnchorTask 应用阐明，敬请期待。

如果你感觉对你有所帮忙，能够关注我的微信公众号徐公

关于android:Android-启动优化二-拓扑排序的原理以及解题思路

前言

基本概念

实战

BFS 算法

题目剖析

BFS 前筹备工作

解题思路

DFS 解法

算法思维

总结

ps