BFS-Traversierung von gerichteten Graphen von einem bestimmten Knoten

Mein Verständnis der Grundlagen der Breite-zuerst-Suche Traversierung für einen Graphen ist:

BFS        
    Start from any node. 
    Add it to queue. 
    Add it to visited array.

    While queue is not empty:
        Remove head from queue; 
        Print node.

        add all unvisited direct subchilds to que; 
        mark them as visited

Jedoch, wenn wir durchqueren gerichtet Graphen von einem bestimmten Knoten und nicht alle Knoten erreichbar sind, die aus den gegebenen Knoten (direkt oder indirekt), wie nutzen wir das BFS für das Durchlaufen der graph dieser situation?

Können Sie bitte erklären, in diesem graph auch: 

a=> b => d => e => d  
a=> c => d

Hier, wenn der Startknoten ist b wir nie drucken a und c.

Bin ich etwas fehlt in dem Algorithmus?

Ich verwendet HashMap<String, ArrayList> adj = new HashMap(); erstellen des angrenzens Liste zum speichern von Graphen.

  • Nein, du bist an nichts fehlt. Wenn der Knoten nicht erreichbar sind, ist die Suche nicht findet.
InformationsquelleAutor user309687 | 2010-04-06
  1. 1

    Jedoch, wenn wir durchqueren einen GERICHTETEN Graphen von einem bestimmten Knoten und nicht alle Knoten zugänglich sind, die von dem gegebenen Knoten [direkt oder indirekt] wie gehen wir mit dem BFS für die gleichen.

    Einen Suchalgorithmus durchläuft ein Diagramm. Wenn Sie Ränder haben, die nicht befahren werden, und damit Knoten, die nicht erreicht werden, wird die Suche einfach nicht finden.

    InformationsquelleAutor Thilo
  2. 0

    Sind Sie richtig in Ihrem Verständnis, außer für den "Start von einem beliebigen Knoten" Teil-eine BFS-Traversierung beginnen muss vom root-Knoten. Also in deinem Beispiel würden Sie haben beginnen mit den Knoten a, sonst, wie Sie gesagt haben, Sie nie besuchen.

    • Das gleiche gilt für die Tiefe-zuerst-Suche, auch.
    • Graphen müssen nicht unbedingt root-Knoten. Die Frage ist, deutlich über Graphen.
    • Allerdings, die Frage, von was ich sehen kann, ist über DAGs DAGs und ein oder mehrere root-Knoten (und wenn es mehr als eine root-Knoten, jede graph-search-Algorithmus vermissen werden einige Knoten, es sei denn, alle root-Knoten Hinzugefügt werden, um die erste Reihe).
    • Vielen Dank für Ihre Kommentare . Ich bin sicher, dass dieses Problem konfrontiert werden würde in der Anzahl der wirklichen Probleme. Gibt es irgendeinen Algorithmus zu finden, einen root-Knoten, in DAGs. Ich möchte zum Durchlaufen des kompletten Graphen aus einer Wurzel, ähnlich wie bei "Test bipartiteness" - problem. Dank
    InformationsquelleAutor RarrRarrRarr
Schreibe einen Kommentar