## 圖的拓撲排序 一些事物，其中某些事物必須在另一些事物完成之后才能開始，一定是無環的有向圖，稱為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; } ~~~