## 图的拓扑排序 一些事物，其中某些事物必须在另一些事物完成之后才能开始，一定是无环的有向图，称为AOV网。其顺序称为图的拓扑序列。 比如如下图： （可以看做是1依赖2和3的编译，2依赖3和4的编译，3依赖4的编译，4依赖5的编译。）  那么拓扑排序之后得到顺序为：1->2->3->4->5。 ## 实用范围 1. 有向图 2. 无环图 ## Java实现拓扑排序 ~~~ /** * 图的topo排序算法 * 1. 找到入度为0的节点加入到队列 * 2. 取出队列里的点，消除相邻点的影响 * @return 拓扑序列； * null，则说明不是有向无环图 */ public Set<Vertex> kahnPololog(){ Set<Vertex> result = new LinkedHashSet<>(); Queue<Vertex> inZeroQueue = new LinkedList<>(); // 记录顶点的入度 Map<Vertex,Integer> inMap = new HashMap<>(); for(Vertex vertex : vertexs.values()){ inMap.put(vertex,vertex.in); // 如果入度为0加入到队列 if(vertex.in == 0){ inZeroQueue.offer(vertex); } } // 处理如多为0的队列 while (!inZeroQueue.isEmpty()){ Vertex cur = inZeroQueue.poll(); result.add(cur); // 消除掉该顶点相邻的点的入度影响 for(Vertex next : cur.nexts){ inMap.put(next,inMap.get(next) - 1); // 如果入度为零，则加入到队列 if(inMap.get(next) == 0){ inZeroQueue.offer(next); } } } // 如果result的大小等于图里顶点数量，则说明拓扑排序成功，图是有向无环的，反之返回null return result.size() == vertexs.size() ? result : null; } ~~~