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

你的名字 2022-11-02 03:58 130阅读 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, [[1,0]] 
    2输出: [0,1]
    3解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2

1输入: 4, [[1,0],[2,0],[3,1],[3,2]]
    2输出: [0,1,2,3] or [0,2,1,3]
    3解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
    4     因此，一个正确的课程顺序是 [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 门课
 *  我们用 有向图 描述这种 依赖关系 (做事的先后关系)：  
    
    
    ![format_png][]

在有向图中，我们知道，有**入度**和**出度**概念：

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

### BFS 前准备工作 ###

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

### 解题思路 ###

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

1    private  class Solution {
     2        public int[] findOrder(int num, int[][] prerequisites) {
     3
     4            // 计算所有节点的入度，这里用数组代表哈希表，key 是 index， value 是 inDegree[index].实际开发当中，用 HashMap 比较灵活
     5            int[] inDegree = new int[num];
     6            for (int[] array : prerequisites) {
     7                inDegree[array[0]]++;
     8            }
     9
    10            // 找出所有入度为 0 的点，加入到队列当中
    11            Queue<Integer> queue = new ArrayDeque<>();
    12            for (int i = 0; i < inDegree.length; i++) {
    13                if (inDegree[i] == 0) {
    14                    queue.add(i);
    15                }
    16            }
    17
    18            ArrayList<Integer> result = new ArrayList<>();
    19            while (!queue.isEmpty()) {
    20                Integer key = queue.poll();
    21                result.add(key);
    22                // 遍历所有课程
    23                for (int[] p : prerequisites) {
    24                    // 改课程依赖于当前课程 key
    25                    if (key == p[1]) {
    26                        // 入度减一
    27                        inDegree[p[0]]--;
    28                        if (inDegree[p[0]] == 0) {
    29                            queue.offer(p[0]); // 加入到队列当中
    30                        }
    31                    }
    32                }
    33            }
    34
    35            // 数量不相等，说明存在环
    36            if (result.size() != num) {
    37                return new int[0];
    38            }
    39
    40            int[] array = new int[num];
    41            int index = 0;
    42            for (int i : result) {
    43                array[index++] = i;
    44
    45            }
    46
    47            return array;
    48        }
    49    }

## DFS 解法 ##

### 算法思想 ###

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

1// 方法 2：邻接矩阵 + DFS   由于用的数组，每次都要遍历，效率比较低
     2    public int[] findOrder(int numCourses, int[][] prerequisites) {
     3        if (numCourses == 0) return new int[0];
     4        // 建立邻接矩阵
     5        int[][] graph = new int[numCourses][numCourses];
     6        for (int[] p : prerequisites) {
     7            graph[p[1]][p[0]] = 1;
     8        }
     9        // 记录访问状态的数组，访问过了标记 -1，正在访问标记 1，还未访问标记 0
    10        int[] status = new int[numCourses];
    11        Stack<Integer> stack = new Stack<>();  // 用栈保存访问序列
    12        for (int i = 0; i < numCourses; i++) {
    13            if (!dfs(graph, status, i, stack)) return new int[0]; // 只要存在环就返回
    14        }
    15        int[] res = new int[numCourses];
    16        for (int i = 0; i < numCourses; i++) {
    17            res[i] = stack.pop();
    18        }
    19        return res;
    20    }
    21
    22    private boolean dfs(int[][] graph, int[] status, int i, Stack<Integer> stack) {
    23        if (status[i] == 1) return false; // 当前节点在此次 dfs 中正在访问，说明存在环
    24        if (status[i] == -1) return true;
    25
    26        status[i] = 1;
    27        for (int j = 0; j < graph.length; j++) {
    28            // dfs 访问当前课程的后续课程，看是否存在环
    29            if (graph[i][j] == 1 && !dfs(graph, status, j, stack)) return false;
    30        }
    31        status[i] = -1;  // 标记为已访问
    32        stack.push(i);
    33        return true;
    34    }

## 总结 ##

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

### ps ###

AnchorTask 源码已经更新到 github，https://github.com/gdutxiaoxu/AnchorTask，下一篇，将输出 **AnchorTask 使用说明**，敬请期待。

**如果你觉得对你有所帮助，可以关注我的微信公众号*程序员徐公***

## 推荐阅读 ##

[致刚入职场的你 - 程序员的成长笔记][-]

[职场上这四件事，越早知道越好][Link 1]

[拼夕夕事件反思，底层逆袭，靠拼命加班行吗][Link 2]

[面试官：手写生产者消费者模型][Link 3]

[Android 启动优化（一） - 有向无环图][Android _ -]

[Android _ -]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95968cdaed07e1ce56e11cffdb84638092e37aaa300b68f2de7a267aceaf19df152b21825&idx=1&mid=2247484968&scene=21&sn=a7938f7504167110baae12f777b248e7#wechat_redirect
[format_png]: /images/20221024/93e9fb05be784a0793794ca8a7258afd.png
[-]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95dcccdaed4da0943d1ee7cd878112e7c5c41808948a7f777192deda713c007d2af105edc&idx=2&mid=2247484044&scene=21&sn=2cdd885d352636524e86fa71c742382e#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95daacdaed4bc0b7445db3db62a64894957be350bc87f9bc4b3eff2d0f425c54ed5422a8f&idx=2&mid=2247484138&scene=21&sn=5685e895e85ad1a08b30750885f78644#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95953cdaed045b1f7da333bc9efeb4b4458d3a802cbe341c3b6fc5b40dd2f564773cec783&idx=1&mid=2247484947&scene=21&sn=56ce85925bee8637b0a90938d21785ac#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95aadcdaed3bb707f2ed96306ea5462ea1e9ce20b71b6af158372d53644396998b78416e9&idx=1&mid=2247484909&scene=21&sn=e83b7b0e69fb630c4549ef9b23c79793#wechat_redirect