拓撲爲了使用BFS

以下問題在塞奇威克和韋恩本書算法被發現在Java中：拓撲爲了使用BFS

4.2.19拓撲排序和BFS。解釋爲什麼以下算法不一定會產生拓撲順序：運行BFS，並通過增加到它們各自源的距離來標記頂點。

我試圖證明它找到一個反例。但是，每次嘗試，我都會得到一個拓撲順序。我的意思是，我不明白爲什麼這不起作用：如果一個頂點的源頭出現在它之前，爲什麼我們沒有一個拓撲順序？

我認爲要證明這一點，我們需要找到一個其來源之前的頂點，但我不能。

任何人都有反例嗎？提前致謝！

PS：這不是功課

@Edit：我試圖樣1 <的哈密爾頓路徑 - 2 < - 0 < - 3 < - 4，它給出0 3 4 2 1 ，但改變0 3和4的位置給了我一個拓撲順序（但是，按照我得到的順序，它不是）。那麼我不確定這是否是一種拓撲順序。

來源

2015-06-16 Giiovanna

您不能使用BFS，因爲具有較高排名的節點可能具有較低排名的事件邊緣。這裏有一個例子：

假設你在源（A）處啓動BFS。 DAG

使用您提出的算法，節點D會出現在節點C之前，這顯然不是拓撲順序。你真的必須使用DFS。

來源

2015-06-16 14:16:24 adao7000

rank是什麼定義？我只知道樹木的等級。而且，如果D出現在A的鄰接列表上，那麼D可能會出現在C之前，對嗎？ – Giiovanna

Rank可以被認爲是一個節點在BFS中處理的「級別」。 A會有1級，B和D會有2級，等等。 – adao7000

好的，非常感謝！ – Giiovanna

-2

反例：

A -> B 
A -> C 
B -> C

BFS開始A能找到的節點，以便A-B-C或A-C-B，但其中只有一個是拓撲排序。

來源

2015-06-16 14:17:14

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

你需要開始與節點其中入度是，這意味着沒有其他節點直接到他們。請務必首先將這些節點添加到結果中。您可以使用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; 
}

來源

2017-07-08 13:04:29

拓撲爲了使用BFS

回答

相關問題