Topologische Suche und Breite erste Suche

Question

Ist es möglich, die erste Suchlogik von Brittth zu verwenden, um eine topologische DAG zu erstellen? Die Lösung in Cormen nutzt Tiefensuche zuerst, wäre aber nicht einfacher zu verwenden BFS?

Grund: BFS besucht alle Knoten in einer bestimmten Tiefe, bevor Knoten mit dem nächsten Tiefenwert aufgerufen werden. Es bedeutet natürlich, dass die Eltern vor den Kindern aufgelistet werden, wenn wir ein BFS machen. Ist das nicht genau das, was wir für eine topologische Sortierung benötigen?

Answer 1

In einem BFS landen alle Kanten, die Sie tatsächlich laufen, in der richtigen Richtung. Aber alle Kanten, die Sie nicht gehen (die zwischen Knoten in der gleichen Tiefe oder die von tieferen Knoten zurück zu früheren Knoten) werden am Ende in die falsche Richtung gehen, wenn Sie das Diagramm in BFS-Reihenfolge anlegen.

Ja, Sie brauchen wirklich DFS, um es zu tun.

Answer 2

Es ist möglich, sogar wikipedia describes an algorithm based on BFS.

Grundsätzlich verwenden Sie eine Warteschlange, in die Sie alle Knoten ohne eingehende Kanten einfügen. Wenn Sie dann einen Knoten extrahieren, entfernen Sie alle seine ausgehenden Kanten und fügen die Knoten ein, die von ihm erreichbar sind und keine anderen eingehenden Kanten haben.

Answer 3

eine bloße BFS ist nur für einen Baum ausreichend (oder Wald von Bäumen), weil in (Wald) Bäume, in Grad höchstens 1. Nun sind in diesem Fall aussehen:

B → C → D 
     ↗ 
    A 

Ein BFS, bei dem die Warteschlange auf A B initialisiert wird (deren In-Grad-Werte 0 sind), gibt A B D C zurück, das nicht topologisch sortiert ist. Deshalb müssen Sie die In-Grad-Zählung beibehalten und nur Knoten auswählen, deren Anzahl auf Null gefallen ist. (*)

BTW, das ist der Fehler Ihres 'Grundes': BFS garantiert nur, dass ein Elternteil vorher besucht wurde, nicht alle.

bearbeiten: (*) Mit anderen Worten drücken Sie benachbarte Knoten, deren in-Grad-Null zurück (in der exemple, nach A Verarbeitung würde D übersprungen). Sie verwenden also immer noch eine Warteschlange, und Sie haben dem allgemeinen Algorithmus gerade einen Filterschritt hinzugefügt. Davon abgesehen ist es weiterhin fragwürdig, es weiterhin als BFS zu bezeichnen.

Answer 4

Ja, Sie können topologische Sortierung mit BFS durchführen. Eigentlich erinnerte ich mich, als mein Lehrer mir sagte, dass, wenn das Problem durch BFS gelöst werden kann, nie wählen, es durch DFS zu lösen. Weil die Logik für BFS einfacher als DFS ist, werden Sie die meiste Zeit immer eine einfache Lösung für ein Problem wünschen.

Wie YvesgereY und IVlad erwähnt, müssen Sie mit Knoten, von denen die indegree ist , dh keine anderen Knoten leiten, um sie zu starten. Stellen Sie sicher, dass Sie diese Knoten zuerst zu Ihrem Ergebnis hinzufügen. Sie können eine HashMap verwenden, um jeden Knoten mit seiner Unabhängigkeit und einer Warteschlange, die sehr häufig in BFS angezeigt wird, um Ihre Traversierung zu unterstützen, verwenden. Wenn Sie einen Knoten aus der Warteschlange abfragen, muss der Abstand seiner Nachbarn um 1 verringert werden. Dies ist wie Löschen des Knotens aus dem Diagramm und Löschen der Kante zwischen dem Knoten und seinen Nachbarn. Jedes Mal, wenn Sie Knoten mit 0 indegree finden, bieten Sie sie der Warteschlange an, um später ihre Nachbarn zu überprüfen und sie zum Ergebnis hinzuzufügen.

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; 
}