程序员徐公

微信公众号:【徐公】

0%

Android 启动优化(二) - 拓扑排序的原理以及解题思路

重要概念

在上一篇文章中 Android 启动优化(一) - 有向无环图,我们介绍了有向无环图,以及拓扑排序的两种解法。今天,让我们一起来实战一下。

基本概念

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

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

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

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

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

实战

我们已 leetcode 上面的一道算法题目作为切入点进行讲解。

leeocode 210: https://leetcode-cn.com/problems/course-schedule-ii/

eg: 现在你总共有 n 门课需要选,记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]

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

可能会有多个正确的顺序,你只要返回一种就可以了。如果不可能完成所有课程,返回一个空数组。

示例 1

1
2
3
输入: 2, [[1,0]] 
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。

示例 2

1
2
3
4
输入: 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] 。

这道题,很明显,看起来可以有有向无环图的解法来解决

BFS 算法

题目分析

我们首先引入有向图 描述依赖关系

示例:假设 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

BFS 前准备工作

  • 我们关心 课程的入度 —— 该值要被减,要被监控
  • 我们关心 课程之间的依赖关系 —— 选这门课会减小哪些课的入度
  • 因此我们需要合适的数据结构,去存储这些关系,这个可以通过哈希表

解题思路

  • 维护一个 queue,里面都是入度为 0 的课程
  • 选择一门课,就让它出列,同时 查看哈希表,看它 对应哪些后续课
  • 将这些后续课的 入度 - 1,如果有减至 0 的,就将它推入 queue
  • 不再有新的入度 0 的课入列 时,此时 queue 为空,退出循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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;
}
}

DFS 解法

算法思想

  • 对图执行深度优先搜索。
  • 在执行深度优先搜索时,若某个顶点不能继续前进,即顶点的出度为0,则将此顶点入栈。
  • 最后得到栈中顺序的逆序即为拓扑排序顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 方法 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 法。其中,入度表法很重要,必须掌握。下一篇,我们将从 项目实战的角度来讲解,怎样搭建一个有向无环图的通用框架,敬请期待。