要求：一定是有向无环图
1)在图中找到所有入度为0的点输出
2)把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始
3)图的所有点都被删除后，依次输出的顺序就是拓扑排序
应用：事件安排、编译顺序
分析：
1 准备一个HashMap，key是某个结点，value是某个结点的剩余入度；再准备一个队列，只有入度为零的结点才进入这个对队列。
2 一开始遍历图中所有的点集，每个点的入度就是默认原来的；一开始肯定有入度为零的结点，所以将其加入队列
3 准备一个列表，用来接收队列弹出的结点，因为队列中的顺序就是拓扑排序的顺序
4 队列不为空的时候，就弹出；并且让列表接收。然后遍历弹出结点的所有直接邻居（就是弹出结点的邻接点），将所有邻接点的入度都减一；之后HashMap表里面再有入度为零的点就继续加入队列…
5最后返回列表，就是拓扑排序的结果
package com.harrison.class11; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Queue; import com.harrison.class11.Code01_NodeEdgeGraph.Graph; import com.harrison.class11.Code01_NodeEdgeGraph.Node; public class Code04_TopologySort { public static List<Node> topologySort(Graph graph){ HashMap<Node, Integer> inMap=new HashMap<>(); Queue<Node> zeroInQueue=new LinkedList<>(); for(Node node:graph.nodes.values()) { inMap.put(node, node.in); if(node.in==0) { zeroInQueue.add(node); } } List<Node> ans=new LinkedList<>(); while(!zeroInQueue.isEmpty()) { Node cur=zeroInQueue.poll(); ans.add(cur); for(Node next:cur.nexts) { inMap.put(next, inMap.get(next)-1); if(inMap.get(next)==0) { zeroInQueue.add(next); } } } return ans; } }
