Bekommen Sie DFS-wenn Sie beim ändern der Warteschlange in einem stack in einem BFS-Implementierung?

Question

Hier ist die standard-pseudocode für Breite erste Suche:

{ seen(x) is false for all x at this point }
push(q, x0)
seen(x0) := true
while (!empty(q))
  x := pop(q)
  visit(x)
  for each y reachable from x by one edge
    if not seen(y)
      push(q, y)
      seen(y) := true

Hier push und pop angenommen, queue-Operationen.Aber was ist, wenn Sie stack-Operationen?Hat der resultierende Algorithmus besuchen Sie die Scheitelpunkte in depth-first order?

---

Wenn Sie stimmten für den Kommentar "das ist trivial", würde ich Sie bitten, zu erklären, warum es einfach ist.Ich finde das problem ziemlich heikel.

Answer 1

Nein, das ist nicht das gleiche wie ein DFS.

Betrachten Sie den graph

Wenn Sie drücken Sie die Knoten in der rechten zur linken um, der Algorithmus gibt Ihnen einen traversal:

$A, B , E, C , D$

während ein DFS-es erwarten würde

$A,B,E,D,C$

Das problem tritt auf, weil Sie es markieren als gesehen auf die Zeit drängen, anstatt die Zeit zu besuchen.Wie bereits in den Kommentaren, wenn Sie mal an der Zeit, den Besuch, den Raumbedarf kann gehen bis zu $ heta(V+E)$ anstatt von $\mathcal{O}(V)$.

Ich Stimme zu, das problem ist nicht trivial.