启动优化 - 有向无环图 android后端

文章图片

前言说到 Android 启动优化，大家第一时间可能会想到异步加载。将耗时任务放到子线程加载，等到所有加载任务加载完成之后，再进入首页。
多线程异步加载方案确实是 ok 的。但如果遇到前后依赖的关系呢。比如任务2 依赖于任务 1，这时候要怎么解决呢。
最简单的方案是将任务1 丢到主线程加载，然后再启动多线程异步加载。
如果遇到更复杂的依赖呢。
任务3 依赖于任务 2，任务 2 依赖于任务 1 呢，这时候你要怎么解决。更复杂的依赖关系呢

文章图片

总不能将任务 2，任务 3 都放到主线程加载吧，这样多线程加载的意义就不大了。
有没有更好的方案呢？
答案肯定是有的，使用有向无环图。它可以完美解决先后依赖关系。
重要概念有向无环图（Directed Acyclic Graph, DAG）是有向图的一种，字面意思的理解就是图中没有环。常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。

文章图片

顶点：图中的一个点，比如顶点 1，顶点 2。
边：连接两个顶点的线段叫做边，edge。
入度：代表当前有多少边指向它。
在上图中，顶掉 1 的入度是 0，因为没有任何边指向它。顶掉 2 的入度是 1，因为顶掉 1 指向顶掉 2. 同理可得出 5 的入度是 2，因为顶掉 4 和顶点 3 指向它
拓扑排序：拓扑排序是对一个有向图构造拓扑序列的过程。它具有如下特点。

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

由于有这个特点，因此常常用有向无环图的数据结构用来解决依赖关系。
上图中，拓扑排序之后，任务2肯定排在任务1之后，因为任务2依赖任务1，任务3肯定在任务2之后，因为任务3依赖任务2。
拓扑排序一般有两种算法，第一种是入度表法，第二种是 DFS 方法。下面，让我们一起来看一下怎么实现它。
入度表法入度表法是根据顶点的入度来判断是否有依赖关系的。若顶点的入度不为 0，则表示它有前置依赖。它也常常被称作 BFS 算法
算法思想

建立入度表，入度为 0 的节点先入队
当队列不为空，进行循环判断
节点出队，添加到结果 list 当中
将该节点的邻居入度减 1
若邻居节点入度为 0，加入队列
若结果 list 与所有节点数量相等，则证明不存在环。否则，存在环

实例讲解
下图所示的有向无环图，采用入度表的方法获取拓扑排序过程。

文章图片

首先，我们选择入度为 0 的顶点，这里顶点 1 的入度为 0，删除顶点 1 之后，图变成如下。

文章图片

这时候，顶点 2 和顶点 4 的入度都为 0，我们可以随便删除一个顶点。（这也就是为什么图的拓扑排序不是唯一的原因）。这里我们删除顶点 2，图变成如下：

文章图片

这时候，我们再删除顶点 4，图变成如下：

文章图片

选择入度为 0 的顶点 3，删除顶点 3 之后，图标称如下，

文章图片

最后剩余顶点5，输出顶点5，拓扑排序过程结束。最终的输出结果为：

文章图片

到此，优先无环图的入度法的流程已经讲解完毕。你清楚了嘛。
代码的话，下期会一起给出。
时间复杂度
设 AOE 网有 n 个事件，e 个活动，则算法的主要执行是：

求每个事件的ve值和vl值：时间复杂度是O(n+e) ；
根据ve值和vl值找关键活动：时间复杂度是O(n+e) ；

因此，整个算法的时间复杂度是O(n+e)
DFS 算法从上面的入度表法，我们可以知道，要得到有向无环图的拓扑排序，我们的关键点要找到入度为 0 的顶点。然后接着删除该结点的相邻所有边。再遍历所有结点。直到入度为 0 的队列为空。这种方法其实是 BFS。
说到 BFS，我们第一时间就想到 DFS。与 BFS 不同的是，DFS 的关键点在于找到，出度为0的顶点。
总结如下，深度优先搜索过程中，当到达出度为0的顶点时，需要进行回退。在执行回退时记录出度为0的顶点，将其入栈。则最终出栈顺序的逆序即为拓扑排序序列。
算法思想

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

实例讲解
同样，以下图讲解 DFS 算法的过程。

文章图片

(1) 从顶点 1 开始出发，开始执行深度优先搜索。顺序为1->2->3->5。
（2）深度优先搜索到达顶点5时，顶点5出度为0。将顶点5入栈。
（3）深度优先搜索执行回退，回退至顶点3。此时顶点3的出度为0，将顶点3入栈。

文章图片

（4）回退至顶点2，顶点2出度为0，顶点2入栈。

文章图片

（5）回退至顶点1，顶点1可以前进位置为顶点4，顺序为1->4。
（6）顶点4出度为0，顶点4入栈。

文章图片

（7）回退至顶点1，顶点1出度为0，顶点1入栈。

文章图片

（8）栈的逆序为1->4->2->3->5。此顺序为拓扑排序结果。

文章图片

时间复杂度
时间复杂度分析：首先深度优先搜索的时间复杂度为O(V+E)，而每次只需将完成访问的顶点存入数组中，需要O(1)，因而总复杂度为O(V+E)。
小结有向无环图的拓扑排序其实并不难，难度中等。通常，我们一般使用 BFS 算法来解决，DFS 算法比较少用。
对于 BFS（入度表法），它的核心思想是

选择一个没有输入边（入度为0）的源顶点（若有多个则任选一个），
将它和它的输出边删除。重复源顶点的删除操作，直到不存在入度为0的源顶点为止。
最终，检测图中的顶点个数，若还有顶点存在则算法无解，否则顶点的删除顺序就是拓扑排序的输出顺序。

https://github.com/gdutxiaoxu...
Android高级开发系统进阶笔记、最新面试复习笔记PDF，我的GitHub
文末 【启动优化 - 有向无环图】您的点赞收藏就是对我最大的鼓励！
欢迎关注我，分享Android干货，交流Android技术。
对文章有何见解，或者有何技术问题，欢迎在评论区一起留言讨论！