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/problems/course-schedule-ii/
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] ，
這道題，很明顯，看起來可以有有向無環圖的解法來解決
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 為空，退出回圈
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，則將此頂點入堆疊，
- 最后得到堆疊中順序的逆序即為拓撲排序順序，
// 方法 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 法，其中，入度表法很重要，必須掌握，下一篇，我們將從 專案實戰的角度來講解，怎樣搭建一個有向無環圖的通用框架，敬請期待，
ps
AnchorTask 原始碼已經更新到 github，AnchorTask，下一篇，將輸出 AnchorTask 使用說明，敬請期待，
如果你覺得對你有所幫助，可以關注我的微信公眾號徐公
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/544797.html
標籤：Android
上一篇：scrollView 嵌套 recyclerview 時 BaseQuickAdapter 九宮格圖片拖拽到底部洗掉