拓撲搜索和廣度優先搜索

Question

是否可以使用廣度優先搜索邏輯來進行拓撲排序的DAG？ Cormen的解決方案利用深度優先搜索，但不會更容易使用BFS？

原因： 在訪問具有下一個深度值的節點之前，BFS訪問特定深度的所有節點。這自然意味着如果我們做了BFS，父母會被列在孩子面前。這不正是我們所需要的拓撲排序嗎？

Answer 1

在BFS中，您實際走過的所有邊都會以正確的方向結束。但是，如果您按照BFS順序佈置圖形，則所有不走路的邊緣（深度相同的節點之間的節點，或者從深度較深的節點返回到較早節點的節點）最終會走錯方向。

是的，你真的需要DFS來做到這一點。

Answer 2

這是可能的，甚至維基百科describes an algorithm based on BFS。

基本上，您使用插入所有節點而沒有傳入邊的隊列。然後，當您提取一個節點時，您將刪除其所有傳出邊，並插入可達到的沒有其他傳入邊的節點。

Answer 3

區區BFS只對一棵樹足夠的（或樹木的森林），因爲（森林）樹，在度至多1 現在，看看這個案例：

B → C → D 
     ↗ 
    A 

將隊列初始化爲A B（其度數爲零）的BFS將返回A B D C，該值未進行拓撲排序。這就是爲什麼你必須保持在度數計數，並只選擇計數已降到零的節點。 （*）

順便說一下，這是你的'理由'的缺陷：BFS只保證一位家長以前曾訪問過，而不是所有的。

編輯：（*）換句話說，你推回相鄰節點，其在度爲零（在爲例，處理後A，D將被跳過）。所以，你仍然在使用一個隊列，並且你已經爲通用算法添加了一個過濾步驟。這就是說，繼續稱它爲BFS是值得懷疑的。

Answer 4

是的，你可以使用BFS做拓撲排序。其實我記得有一次我的老師告訴我，如果問題可以通過BFS解決，千萬別選擇通過DFS解決。因爲BFS的邏輯比DFS簡單，大多數情況下您總是需要一個直接解決問題的方法。

由於YvesgereY和IVlad提到，你需要開始與節點其中入度是，這意味着沒有其他節點直接到他們。請務必首先將這些節點添加到結果中。您可以使用HashMap將每個節點與它的indegree進行映射，並使用BFS中常見的隊列來協助您的遍歷。當您從隊列中輪詢一個節點時，其鄰居的不完整性需要減1，這就像從圖中刪除節點並刪除節點與其鄰居之間的邊。每次遇到0度的節點時，將它們提供給隊列以稍後檢查其鄰居並將它們添加到結果中。

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) { 

    ArrayList<DirectedGraphNode> result = new ArrayList<>(); 
    if (graph == null || graph.size() == 0) { 
     return result; 
    } 
    Map<DirectedGraphNode, Integer> indegree = new HashMap<DirectedGraphNode, Integer>(); 
    Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>(); 

    //mapping node to its indegree to the HashMap, however these nodes 
    //have to be directed to by one other node, nodes whose indegree == 0 
    //would not be mapped. 
    for (DirectedGraphNode DAGNode : graph){ 
     for (DirectedGraphNode nei : DAGNode.neighbors){ 
      if(indegree.containsKey(nei)){ 
       indegree.put(nei, indegree.get(nei) + 1); 
      } else { 
       indegree.put(nei, 1); 
      } 
     } 
    } 


    //find all nodes with indegree == 0. They should be at starting positon in the result 
    for (DirectedGraphNode GraphNode : graph) { 
     if (!indegree.containsKey(GraphNode)){ 
      queue.offer(GraphNode); 
      result.add(GraphNode); 
     } 
    } 


    //everytime we poll out a node from the queue, it means we delete it from the 
    //graph, we will minus its neighbors indegree by one, this is the same meaning 
    //as we delete the edge from the node to its neighbors. 
    while (!queue.isEmpty()) { 
     DirectedGraphNode temp = queue.poll(); 
     for (DirectedGraphNode neighbor : temp.neighbors){ 
      indegree.put(neighbor, indegree.get(neighbor) - 1); 
      if (indegree.get(neighbor) == 0){ 
       result.add(neighbor); 
       queue.offer(neighbor); 
      } 
     } 
    } 
    return result; 
}