Durchführung von DFS und BFS auf einen gerichteten Graphen

Angenommen wir haben einen Graphen wie:

Durchführung von DFS und BFS auf einen gerichteten Graphen

Wenn Sie wollten, ein Pfad von 0 bis 5, in welcher Reihenfolge wir besuchen die Knoten, wenn wir DFS-und BFS auf dieser Grafik (angenommen, die tiefste element wird immer zuerst betätigt). Ich habe Schwierigkeiten, die Konzeptualisierung, wie die algorithmen funktionieren wird für einen Graphen mit Zyklen, und ich hatte gehofft, jemand könnte beschreiben das Verfahren nimmt jeweils einen solchen Graphen.

InformationsquelleAutor Bob John | 2013-04-28
  1. 4

    Gemeinsame Technik, die verwendet wird, um mit viel Zyklen ist mit der bereits besuchten Ecken. Bevor Sie push-vertex auf die queue/stack überprüfen, ob er besucht wurde. Wenn es nicht tun, jede Aktion, ansonsten start aus, indem es auf besucht gesetzt und dann weiter die Traversierung von Graphen.

    Stack von oben nach unten.

    DFS:

    empty stack
visiting 0: stack: 2, 1, visited: 0
visiting 2: stack: 5, 3, 1 visited: 0, 2
visiting 5: stack: 4, 3, 1 visited: 0, 2, 5
visiting 4: stack: 3, 2, 3, 1 visited: 0, 2, 4, 5
visiting 3: stack: 4, 2, 3, 1 visited: 0, 2, 3, 4, 5
visiting 4: (nothing to do) - stack: 2, 3, 1 visited: 0, 2, 3, 4, 5
visiting 2: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5
visiting 3: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5
visiting 1: stack: 3, 0 visited: 0, 1, 2, 3, 4, 5
visiting 3: (nothing to do) - stack: 1 visited: 0, 1, 2, 3, 4, 5
visiting 1: (nothing to do) - stack empty visited: 0, 1, 2, 3, 4, 5
DONE

    In ähnlicher Weise tun, für die BFS.

    InformationsquelleAutor Adrian
Schreibe einen Kommentar