Erhalten Sie DFS, wenn Sie die Warteschlange in einer BFS-Implementierung in einen Stapel ändern?

Hier ist der Standard-Pseudocode für die Breitensuche:

{ 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 pushund popwerden Warteschlangenoperationen angenommen. Aber was ist, wenn es sich um Stapeloperationen handelt? Besucht der resultierende Algorithmus Eckpunkte in der Reihenfolge der Tiefe zuerst?

Wenn Sie für den Kommentar "das ist trivial" gestimmt haben, würde ich Sie bitten zu erklären, warum es trivial ist. Ich finde das Problem ziemlich knifflig.

algorithms graphs rgrig
quelle

Ich habe Schüler gesehen, die damit zu kämpfen hatten, deshalb halte ich es nicht für zu einfach. Was mehr als "Ja" oder "Nein" sollte eine Antwort enthalten? Die gewünschte Granularität ergibt sich nicht aus der Frage.

Raphael

"Ja" würde mit einem überzeugenden Argument kommen; "nein" würde mit einem Gegenbeispiel kommen. Aber es gibt bessere Antworten als Ja / Nein, sobald Sie verstehen, was los ist ...

Rgrig

@ Joe, Dave: Sehen Sie sich bitte die folgende

Gilles 'SO - hören Sie auf, böse zu sein'

Es ist möglich, Pseudo-Code zu schreiben, sodass popwir durch einfaches Wechseln in einen Stapel oder eine Warteschlangenoperation dfs oder bfs erhalten. Es ist auch einfach, Pseudo-Code zu schreiben, für den es auf den ersten Blick so aussieht, als ob dies wahr ist, aber es ist nicht wahr. ics.uci.edu//~eppstein/161/960215.html ist eine relevante Referenz.

Joe

Antworten:

Nein, dies ist nicht dasselbe wie eine DFS.

Betrachten Sie die Grafik

Bildbeschreibung hier eingeben

Wenn Sie die Knoten in der Reihenfolge von rechts nach links verschieben, werden Sie vom Algorithmus durchlaufen:

$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 als gesehen zum Zeitpunkt des Pushings und nicht zum Zeitpunkt des Besuchs markieren. Wie in den Kommentaren erwähnt, kann Ihr Platzbedarf zum Zeitpunkt des Besuchs bei und nicht bei . $\Theta(V+E)$ $\mathcal{O}(V)$

Ich stimme zu, das Problem ist nicht trivial.

Aryabhata
quelle

Dies setzt voraus, dass die Adjazenzlisten eine bestimmte feste Reihenfolge haben. Zumindest in der Mathematik betrachtet man sie als Menge, und ein Diagramm hat mehrere Durchquerungen in Tiefenordnung, je nachdem, wie Sie die untergeordneten Elemente iterieren. (Stellen Sie sich vor, Sie verwenden Hashes für Kinder.) In diesem Sinne ist ABECD immer noch eine tiefgreifende erste Ordnung. Der Fragesteller fragt sich, ob es auch in dieser Situation ein Gegenbeispiel gibt. (In der Tat, hier beginnt es schwierig zu werden.)

Rgrig

@rgrig: Nun, dies ist eine der möglichen Überquerungen, und das führt zu einer Sequenz, die nicht in DFS enthalten ist. Unabhängig davon, wie Sie iterieren, führt das Markieren von als gesehen dazu, dass die DFS "unter" falsch ausgegeben wird, wenn Sie nicht zuerst besuchen .

D

$D$

E

$E$

D

$D$

Aryabhata

@Arybhata: Oh, tut mir leid, ich weiß nicht, warum ich angenommen habe, dass Sie beabsichtigten, dass die Kanten gerichtet sind und nach unten zeigen. Sie sind ungerichtet, also haben Sie Recht: Dies ist ein Gegenbeispiel, auch für das, was ich in dem Kommentar gesagt habe. (Das ist seltsam: Ich musste Ihren Griff falsch

schreiben