思路： 1、用字典存儲每個節點的入度 2、用隊列存儲入度為零的節點 3、BFS
static public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) { // write your code here //返回的值 ArrayList<DirectedGraphNode> ret=new ArrayList<>(); //隊列 Queue<DirectedGraphNode> que=new LinkedList<>(); //字典 HashMap<DirectedGraphNode, Integer> dict=new HashMap<>(); //入度的計算 for(DirectedGraphNode k : graph) { if(!dict.containsKey(k)) { dict.put(k, 0); for(DirectedGraphNode m:k.neighbors) { if(!dict.containsKey(m)) dict.put(m, 1); else { dict.put(m, dict.get(m)+1); } } } else { for(DirectedGraphNode m:k.neighbors) { if(!dict.containsKey(m)) dict.put(m, 1); else { dict.put(m, dict.get(m)+1); } } } } //將所有最開始入度就為零的節點放到隊列里 for(DirectedGraphNode n:dict.keySet()) { if(dict.get(n).equals(0)) { que.add(n); } } //進行主要的循環部分，實現輸出 while(!que.isEmpty()) { DirectedGraphNode temp=que.poll();//將隊列取出一個 ret.add(temp);//輸出：放到ret返回值里 //將輸出節點的下一個節點入度減一 for(DirectedGraphNode m : temp.neighbors) { dict.put(m,dict.get(m)-1); if(dict.get(m)==0)//如果減一后入度為0 que.add(m);//就放到隊列中 } } //最終返回 return ret; }新聞熱點
疑難解答
