Czy otrzymujesz DFS, jeśli zmienisz kolejkę na stos w implementacji BFS?

Oto standardowy pseudokod pierwszego wyszukiwania szerokości:

{ 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

Tutaj pushi popzakłada się, że są to operacje kolejkowe. Ale co jeśli są operacjami stosowymi? Czy wynikowy algorytm odwiedza wierzchołki w pierwszej kolejności według głębokości?

Jeśli głosowałeś na komentarz „to jest trywialne”, proszę o wyjaśnienie, dlaczego jest to trywialne. Uważam, że problem jest dość trudny.

algorithms graphs rgrig
źródło

Widziałem, jak studenci zmagają się z tym, więc nie sądzę, że jest to zbyt proste. Jednak co więcej niż „Tak” lub „Nie” powinna zawierać odpowiedź? Pożądana ziarnistość nie wynika jasno z pytania.

Raphael

„Tak” przychodzi z przekonującym argumentem; „nie” przyjdzie z kontraprzykładem. Ale są lepsze odpowiedzi niż tak / nie, gdy zrozumiesz, co się dzieje ...

rgrig

@Joe, Dave: zobacz następującą meta dyskusję

Gilles 'SO- przestań być zły'

Możliwe jest napisanie pseudo-kodu, aby po prostu przechodząc popdo operacji stosu lub kolejki otrzymaliśmy dfs lub bfs. Łatwo jest również napisać pseudo-kod, dla którego na pierwszy rzut oka wydaje się, że to prawda, ale tak nie jest. ics.uci.edu//~eppstein/161/960215.html to odpowiednie odniesienie.

Joe

Odpowiedzi:

Nie, to nie to samo co DFS.

Rozważ wykres

wprowadź opis zdjęcia tutaj

Jeśli popchniesz węzły w kolejności od prawej do lewej, algorytm wyświetli przejście:

$A, B , E, C , D$

podczas gdy DFS by się tego spodziewał

$A,B,E,D,C$

Problem występuje, ponieważ oznaczysz go jako widoczny podczas pchania, a nie podczas odwiedzania. Jak wskazano w komentarzach, jeśli zaznaczysz w czasie wizyty, twoje wymagania dotyczące miejsca mogą wzrosnąć do zamiast do . $\Theta(V+E)$ $\mathcal{O}(V)$

Zgadzam się, problem nie jest trywialny.

Aryabhata
źródło

Zakłada się, że listy przyległości mają określoną ustaloną kolejność. Przynajmniej w matematyce jeden z nich traktuje jako zestaw, a wykres zawiera wiele przejść w kolejności głębokości, w zależności od tego, jak zdarzyło się iterować dzieci. (Wyobraź sobie, że używasz skrótów dla dzieci.) W tym sensie ABECD wciąż jest pierwszym porządkiem głębokości. Pytający zastanawia się, czy istnieje nawet kontrprzykład w tym otoczeniu. (Rzeczywiście, tutaj zaczyna się

robić

@rgrig: Cóż, jest to jedno z możliwych przejść, co prowadzi do sekwencji, której nie ma w DFS. Nieważne jak iteracyjne, znakowanie jak widać spowoduje DFS „poniżej” wyjdzie źle, jeśli nie odwiedzić pierwszy.

D

$D$

E

$E$

D

$D$

Aryabhata

@Arybhata: Och, przepraszam, nie wiem, dlaczego zakładałem, że chciałeś, aby krawędzie były skierowane i skierowane w dół. Nie są one przekierowane, więc masz rację: to jest kontrprzykład nawet na to, co mówiłem w komentarzu. (To dziwne: musiałem przeliterować twój uchwyt, żeby nie został usunięty przez SE.)

rgrig