Android 启动优化(二) - 拓扑排序的原理以及解题思路
Android 启动优化(三) - AnchorTask 使用说明
Android 启动优化(四)- 手把手教你实现 AnchorTask
Android 启动优化(五)- AnchorTask 1.0.0 版本更新了
这几篇文章从 0 到 1,讲解 DAG 有向无环图是怎么实现的,以及在 Android 启动优化的应用。
推荐理由:现在挺多文章一谈到启动优化,动不动就聊拓扑结构,这篇文章从数据结构到算法、到设计都给大家说清楚了,开源项目也有非常强的借鉴意义。
春节之前,更新了一篇博客 Android 启动优化(一) - 有向无环图,反响还不错,今天,让我们一起来看一下,怎样用代码实现有向无环图。
拓扑排序的英文名是 Topological sorting。
拓扑排序要解决的问题是给一个图的所有节点排序。有向无环图才有拓扑排序,非有向无环图没有。
换句话说,拓扑排序必须满足以下条件
图必须是一个无环有向图。序列必须满足的条件:
我们已 leetcode 上面的一道算法题目作为切入点进行讲解。
leeocode 210: leetcode-cn.com/problems/co…
eg: 现在你总共有 n 门课需要选,记为?0?到?n-1。
在选修某些课程之前需要一些先修课程。?例如,想要学习课程 0 ,你需要先完成课程?1 ,我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件,返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序,你只要返回一种就可以了。如果不可能完成所有课程,返回一个空数组。
示例 1
示例 2
这道题,很明显,看起来可以有有向无环图的解法来解决
我们首先引入有向图 描述依赖关系
示例:假设 n=6,先决条件表:[ [3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4] ]
在有向图中,我们知道,有入度和出度概念:
如果存在一条有向边 A --> B,则这条边给 A 增加了 1 个出度,给 B 增加了 1 个入度。所以顶点 0、1、2 的 入度为 0。 顶点 3、4、5 的 入度为 2
这篇博客从实战的角度出发,介绍了有向无环图的两种解法,入度表法和 DFS 法。其中,入度表法很重要,必须掌握。下一篇,我们将从 项目实战的角度来讲解,怎样搭建一个有向无环图的通用框架,敬请期待。
AnchorTask 源码已经更新到 github,AnchorTask,下一篇,将输出 AnchorTask 使用说明,敬请期待。
如果你觉得对你有所帮助,可以关注我的微信公众号程序员徐公
我正在参与掘金技术社区创作者签约计划招募活动,点击链接报名投稿。