简介
APP启动时，有很多初始化工作需要进行，例如引入了很多第三方SDK后，都需要在程序启动时进行初始化，这是一个耗时的过程，性能优化时，可以将任务放在子线程，所有任务完成之后，进入主页。但是这样存在一个问题，如果任务之间存在依赖，无法控制初始化顺序。如果放到主线程顺序执行，性能又很差。这个时候就需要启动器，控制初始化顺序。
分析
可以把图中的节点看成是初始化任务，要执行任务3，必须先完成任务0和1，要执行任务4，必须先完成任务1和2，要执行任务5，必须先完成任务3和4。这就是有向无环图的拓扑排序。因此，对于APP的启动器，核心原理就是有向无环图。
有向无环图的拓扑排序，有两种算法：
（1）广度优先算法（BFS）
核心思想：
① 将入度为 0 的所有节点加入到队列；
② 队头任务出队列，将其后续节点的入度-1；
③ 将入度为 0 的节点加入队列；
④ 队列为空，且无入度为 0 的节点
（2）深度优先算法（DFS）
① 对图进行深度遍历，找到最大深度（无法前进）的节点，加入到栈中；
② 对1中进行循环操作，直到所有节点全部入栈；
③ 出栈。出栈顺序即为有向无环图的拓扑
代码
已BFS为例，后续的启动器也会使用BDS算法：
以下图为例：
遍历的顺序应该为G, E, F, D, C, B, A（顺序不唯一）
import java.util.*;
public class Main {
public static void main(String[] args) {
// 存储所有的节点
List<Node> allNodes = new ArrayList<>();
allNodes.add(new Node("A", new ArrayList<>(Arrays.asList("C", "B")), new ArrayList<>()));
allNodes.add(new Node("B", new ArrayList<>(Collections.singletonList("C")), new ArrayList<>(Collections.singletonList("A"))));
allNodes.add(new Node("C", new ArrayList<>(Collections.singletonList("F")), new ArrayList<>(Arrays.asList("B", "A"))));
allNodes.add(new Node("D", new ArrayList<>(Collections.singletonList("E")), new ArrayList<>()));
allNodes.add(new Node("E", new ArrayList<>(Collections.singletonList("G")), new ArrayList<>(Collections.singletonList("D"))));
allNodes.add(new Node("F", new ArrayList<>(Collections.singletonList("G")), new ArrayList<>(Collections.singletonList("C"))));
allNodes.add(new Node("G", new ArrayList<>(), new ArrayList<>(Arrays.asList("E", "F"))));
createDagGraph(allNodes);
}
/**
* 计算所有节点的入度
*
* @param allNodes 所有节点
*/
private static Map<Node, Integer> calculateDegree(List<Node> allNodes,Node removedNode) {
// 存储每个节点的入度
Map<Node, Integer> degreeMap = new HashMap<>();
// 删除节点
allNodes.remove(removedNode);
// 删除边
for (Node node : allNodes) {
List<String> endNodes = node.getAfterNodes();
endNodes.removeIf(endNodeName -> endNodeName.equals(removedNode.getNodeName()));
List<String> beforeNodes = node.getBeforeNodes();
beforeNodes.removeIf(beforeNode -> beforeNode.equals(removedNode.getNodeName()));
}
// 计算入度
for (Node node : allNodes) {
degreeMap.put(node, node.getBeforeNodes().size());
}
return degreeMap;
}
/**
* 构造DAG图
* @param allNodes 所有节点
*/
private static void createDagGraph(List<Node> allNodes) {
// 存储入度为0的节点，先进先出
Queue<Node> zeroNodeQueue = new LinkedList<>();
// 存储最终的顺序
Queue<Node> resultNodeQueue = new LinkedList<>();
// 所有节点的个数
int nodeSize = allNodes.size();
// 将所有入度为0的节点放入队列
for (Node node : allNodes) {
if (node.getBeforeNodes() != null && node.getBeforeNodes().size() == 0){
zeroNodeQueue.add(node);
}
}
while (zeroNodeQueue.size() > 0){
// 如果存在入度为0的节点，就直接出队列
Node outNode = zeroNodeQueue.remove();
System.out.println("遍历节点 = " + outNode.getNodeName());
resultNodeQueue.add(outNode);
// 移除该节点，计算剩余节点的入度，入度为0的加入到队列
Map<Node, Integer> degreeList = calculateDegree(allNodes,outNode);
for (Map.Entry<Node,Integer> entry : degreeList.entrySet()){
if (entry.getValue() == 0 && !zeroNodeQueue.contains(entry.getKey())){
// 入度为 0 的节点
Node node = entry.getKey();
zeroNodeQueue.add(node);
}
}
}
if (resultNodeQueue.size() != nodeSize){
System.out.println("不是有向无环图，存在环");
}
System.out.println("结果 = " + resultNodeQueue);
}
}
/**
* 节点
*/
class Node {
public Node(String nodeName, List<String> beforeNodes, List<String> afterNodes) {
this.nodeName = nodeName;
this.beforeNodes = beforeNodes;
this.afterNodes = afterNodes;
}
private String nodeName;
private List<String> beforeNodes;
private List<String> afterNodes;
public String getNodeName() {
return nodeName;
}
public void setNodeName(String nodeName) {
this.nodeName = nodeName;
}
public List<String> getBeforeNodes() {
return beforeNodes;
}
public void setBeforeNodes(List<String> beforeNodes) {
this.beforeNodes = beforeNodes;
}
public List<String> getAfterNodes() {
return afterNodes;
}
public void setAfterNodes(List<String> afterNodes) {
this.afterNodes = afterNodes;
}
@Override
public String toString() {
return nodeName;
}
}
