要求:一定是有向无环图
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; } }