要求：一定是有向無環圖
1)在圖中找到所有入度為0的點輸出
2)把所有入度為0的點在圖中刪掉，繼續找入度為0的點輸出，周而復始
3)圖的所有點都被洗掉后，依次輸出的順序就是拓撲排序
應用：事件安排、編譯順序
分析：
- 準備一個HashMap，key是某個結點，value是某個結點的剩余入度；再準備一個佇列，只有入度為零的結點才進入這個對佇列，
- 一開始遍歷圖中所有的點集，每個點的入度就是默認原來的；一開始肯定有入度為零的結點，所以將其加入佇列
- 準備一個串列，用來接收佇列彈出的結點，因為佇列中的順序就是拓撲排序的順序
- 佇列不為空的時候，就彈出；并且讓串列接收，然后遍歷彈出結點的所有直接鄰居（就是彈出結點的鄰接點），將所有鄰接點的入度都減一；之后HashMap表里面再有入度為零的點就繼續加入佇列…
- 最后回傳串列，就是拓撲排序的結果
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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/389216.html
標籤：其他
上一篇：QueryDSL中使用的PostgreSQL函式不起作用，回傳ERROR：語法錯誤位于或接近“。”
下一篇：圖的深度優先遍歷