Załóżmy, że chcesz zaimplementować rekurencyjne przeszukiwanie wszerz drzewa binarnego . Jak byś się do tego zabrał?
Czy jest możliwe używanie tylko stosu wywołań jako pamięci dyskowej?
Załóżmy, że chcesz zaimplementować rekurencyjne przeszukiwanie wszerz drzewa binarnego . Jak byś się do tego zabrał?
Czy jest możliwe używanie tylko stosu wywołań jako pamięci dyskowej?
Odpowiedzi:
(Zakładam, że to tylko jakieś ćwiczenie myślowe, a nawet podchwytliwe zadanie domowe / pytanie do rozmowy kwalifikacyjnej, ale przypuszczam, że mógłbym sobie wyobrazić jakiś dziwny scenariusz, w którym z jakiegoś powodu nie masz miejsca na sterty [jakiś naprawdę zły zwyczaj menadżer pamięci? jakieś dziwne problemy ze środowiskiem wykonawczym / systemem operacyjnym?], podczas gdy nadal masz dostęp do stosu ...)
Przechodzenie wszerz tradycyjnie używa kolejki, a nie stosu. Natura kolejki i stosu jest prawie przeciwna, więc próba użycia stosu wywołań (który jest stosem, stąd nazwa) jako pamięci dyskowej (kolejki) jest prawie skazana na niepowodzenie, chyba że robisz coś głupiego absurdalnego ze stosem wywołań, którym nie powinieneś być.
Z tego samego powodu naturą każdej rekursji innej niż ogon, którą próbujesz zaimplementować, jest zasadniczo dodanie stosu do algorytmu. To sprawia, że pierwsze przeszukiwanie w drzewie binarnym nie jest już obszerne, a tym samym czas wykonywania i inne elementy tradycyjnego BFS nie mają już pełnego zastosowania. Oczywiście zawsze można w trywialny sposób przekształcić dowolną pętlę w wywołanie rekurencyjne, ale nie jest to żadna sensowna rekurencja.
Istnieją jednak sposoby, jak pokazali inni, aby zaimplementować coś, co jest zgodne z semantyką BFS za pewną cenę. Jeśli koszt porównania jest drogi, ale przemierzanie węzłów jest tanie, to tak jak zrobił to @Simon Buchan , możesz po prostu uruchomić iteracyjne przeszukiwanie w głąb, przetwarzając tylko liście. Oznaczałoby to brak rosnącej kolejki przechowywanej w stercie, tylko lokalną zmienną głębokości, a stosy są budowane w kółko na stosie wywołań, gdy drzewo jest przechodzone w kółko. I jak zauważył @Patrick , drzewo binarne wspierane przez tablicę jest zwykle przechowywane w kolejności przechodzenia wszerz, więc przeszukiwanie wszerz byłoby trywialne, również bez kolejki pomocniczej.
źródło
Jeśli używasz tablicy do tworzenia kopii zapasowej drzewa binarnego, możesz algebraicznie określić następny węzeł. jeśli
i
jest węzłem, to jego dzieci można znaleźć w2i + 1
(dla lewego węzła) i2i + 2
(dla prawego węzła). Następny sąsiad węzła jest określany przezi + 1
, chyba żei
jest to potęga2
Oto pseudokod dla bardzo naiwnej implementacji pierwszego przeszukiwania wszerz w binarnym drzewie wyszukiwania opartym na tablicy. Zakłada to tablicę o stałym rozmiarze, a zatem drzewo o stałej głębokości. Będzie patrzeć na węzły bez rodzica i może stworzyć niemożliwy do zarządzania duży stos.
źródło
Nie mogłem znaleźć sposobu, aby zrobić to całkowicie rekurencyjnie (bez żadnej pomocniczej struktury danych). Ale jeśli kolejka Q jest przekazywana przez referencję, możesz mieć następującą rekurencyjną funkcję głupiego ogona:
źródło
W poniższej metodzie zastosowano algorytm DFS, aby uzyskać wszystkie węzły na określonej głębokości - co jest takie samo jak wykonanie BFS dla tego poziomu. Jeśli znajdziesz głębokość drzewa i zrobisz to na wszystkich poziomach, wyniki będą takie same jak w przypadku BFS.
Znalezienie głębokości drzewa to bułka z masłem:
źródło
level
zera.Prosta rekurencja BFS i DFS w Javie: po
prostu wypchnij / zaoferuj węzeł główny drzewa w stosie / kolejce i wywołaj te funkcje.
źródło
Znalazłem bardzo piękny, rekurencyjny (a nawet funkcjonalny) algorytm związany z przemierzaniem Breadth-First. Nie mój pomysł, ale myślę, że należy o tym wspomnieć w tym temacie.
Chris Okasaki bardzo wyraźnie wyjaśnia swój algorytm numeracji wszerz z ICFP 2000 pod adresem http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html za pomocą tylko 3 zdjęć.
Implementacja Debasish Ghosh w Scali, którą znalazłem pod adresem http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html , to:
źródło
Głupi sposób:
źródło
Oto krótkie rozwiązanie Scala :
Pomysł wykorzystania wartości zwracanej jako akumulatora jest dobrze dopasowany. Może być zaimplementowany w innych językach w podobny sposób, po prostu upewnij się, że Twoja rekurencyjna funkcja przetwarza listę węzłów .
Listing kodu testowego (przy użyciu drzewa testowego @marco):
Wynik:
źródło
Oto implementacja Pythona:
źródło
Oto implementacja rekurencyjnego BFS w Scali 2.11.4. Poświęciłem optymalizację wywołań ogonowych dla zwięzłości, ale wersja TCOd jest bardzo podobna. Zobacz także post @snv .
źródło
Poniższe wydaje mi się całkiem naturalne, używając Haskella. Iteruj rekurencyjnie po poziomach drzewa (tutaj zbieram nazwy w duży uporządkowany ciąg, aby pokazać ścieżkę przez drzewo):
źródło
Oto implementacja Pythona z rekurencyjnym przechodzeniem przez BFS, pracująca dla wykresu bez cyklu.
źródło
Chciałbym dodać moje centy do górnej odpowiedzi, ponieważ jeśli język obsługuje coś takiego jak generator, bfs można wykonać ko-rekurencyjnie.
Na początek odpowiedź @ Tanzelax brzmi:
Rzeczywiście, zwykły stos wywołań funkcji nie będzie zachowywał się jak zwykły stos. Ale funkcja generatora zawiesi wykonywanie funkcji, więc daje nam szansę na uzyskanie następnego poziomu dzieci węzłów bez zagłębiania się w głębsze potomstwo węzła.
Poniższy kod jest rekurencyjnym bfs w Pythonie.
Oto intuicja:
źródło
Musiałem zaimplementować przemierzanie sterty, które generuje w kolejności BFS. W rzeczywistości nie jest to BFS, ale spełnia to samo zadanie.
źródło
Niech v będzie wierzchołkiem początkowym
Niech G będzie danym wykresem
Poniżej znajduje się pseudokod bez użycia kolejki
źródło
BFS dla drzewa binarnego (lub n-arnego) można wykonać rekurencyjnie bez kolejek w następujący sposób (tutaj w Javie):
Przykładowy wydruk przechodzenia od 1 do 12 w kolejności rosnącej:
źródło
źródło
Oto implementacja JavaScript, która fałszuje Breadth First Traversal z rekursją Depth First. Przechowuję wartości węzłów na każdej głębokości wewnątrz tablicy, wewnątrz skrótu. Jeśli poziom już istnieje (mamy kolizję), po prostu wypychamy do tablicy na tym poziomie. Możesz użyć tablicy zamiast obiektu JavaScript, ponieważ nasze poziomy są numeryczne i mogą służyć jako indeksy tablic. Możesz zwrócić węzły, wartości, przekonwertować na listę połączoną lub cokolwiek chcesz. Zwracam wartości ze względu na prostotę.
Oto przykład rzeczywistego pierwszego przejścia szerokości przy użyciu podejścia iteracyjnego.
źródło
Poniżej znajduje się mój kod do całkowicie rekurencyjnej implementacji przeszukiwania wszerz dwukierunkowego wykresu bez używania pętli i kolejki.
źródło
Implementacja C # rekurencyjnego algorytmu wyszukiwania wszerz dla drzewa binarnego.
Wizualizacja danych drzewa binarnego
Jeśli chcesz, aby algorytm działał nie tylko z drzewem binarnym, ale z wykresami, które mogą mieć dwa i więcej węzłów wskazujących na ten sam inny węzeł, musisz uniknąć samokontroli, utrzymując listę już odwiedzonych węzłów. Implementacja może wyglądać tak.
Wizualizacja danych graficznych
źródło
Zrobiłem program przy użyciu C ++, który działa również na wykresie połączonym i rozłącznym.
źródło