图的拓扑排序算法

拓扑排序
什么是拓扑排序？
比如说，我们平时工作过程中一定听过一个词叫做—不能循环依赖。什么意思？
在这里插入图片描述
A依赖BCD，B依赖CD，C依赖D，D依赖EF，想要获得A的话，首先就要先有EF，有EF -> D -> C ->B -> A。整个这么一个编译的顺序就是拓扑排序。
所以说，拓扑排序就可以理解为是：根据先后顺序能够把工作依次做完，而且不缺依赖的顺序，就是拓扑序。
所以说为什么不能循环依赖，对于拓扑排序来说，一定是有向图并且无环
所以，如果依赖顺序是这样的话，那么就不叫拓扑序了。搞不定先做谁后做谁，互相依赖了。
在这里插入图片描述
练习
图结构如下所示，根据图结构，打印出它的拓扑序。

整体思路是这样：首先找到图中入度为0的（A,B），就是拓扑序中的头。将AB影响消掉，剩C ->D 再找入度为0的（C），再将C的影响消掉，最后剩D。不了解入度概念请看这篇帖子图的适配器。

代码实现
解释一下代码中各个变量。不了解Graph结构的还是请先看图的适配器。

public class Class03_TopologySort {public static List<Node> sortedTopology(Graph graph) {//inMap : 每个点所对应的入度信息//key：各个点的信息。//value: 点所对应的入度值。HashMap<Node, Integer> inMap = new HashMap<>();//如果入度值为0，则进队列中Queue<Node> zeroInQueue = new LinkedList<>();//遍历图中所有的nodesfor (Node node : graph.nodes.values()) {//填充inMapinMap.put(node, node.in);//如果此时入度值为0，直接放入队列中。if (node.in == 0) {zeroInQueue.add(node);}}//result存储的就是最终拓扑序后一个个打印出来的节点的顺序List<Node> result = new ArrayList<>();//如果队列不为nullwhile (!zeroInQueue.isEmpty()) {//弹出，并添加到List中Node cur = zeroInQueue.poll();result.add(cur);//遍历弹出的节点的nextsfor (Node next : cur.nexts) {、//这一步就是将影响消除，将next节点的入度 - 1inMap.put(next, inMap.get(next) - 1);// - 1后如果为0，放入队列中等待遍历添加到resultif (inMap.get(next) == 0) {zeroInQueue.add(next);}}}return result;}
}