Podczas przechodzenia przez drzewo / wykres, jaka jest różnica między Najpierw szerokość i najpierw głębokość? Wszelkie przykłady kodowania lub pseudokodu byłyby świetne.
171
Podczas przechodzenia przez drzewo / wykres, jaka jest różnica między Najpierw szerokość i najpierw głębokość? Wszelkie przykłady kodowania lub pseudokodu byłyby świetne.
Odpowiedzi:
Te dwa terminy rozróżniają dwa różne sposoby chodzenia po drzewie.
Najłatwiej jest chyba pokazać różnicę. Rozważ drzewo:
Głębokość pierwszy przejścia odwiedzi węzły w tej kolejności
Zwróć uwagę, że przed przejściem dalej schodzisz całą nogę w dół .
Szerokość pierwszy przejścia odwiedzi węzeł w tej kolejności
Tutaj pracujemy całą drogę całej każdym poziomie przed zejściem w dół.
(Zauważ, że jest pewna dwuznaczność w kolejności przechodzenia i oszukiwałem, aby utrzymać kolejność „czytania” na każdym poziomie drzewa. W każdym przypadku mogłem dostać się do B przed lub po C, i podobnie mogłem dostać się do E przed lub po F. To może mieć znaczenie lub nie, zależy od twojego zastosowania ...)
Za pomocą pseudokodu można uzyskać oba rodzaje przechodzenia:
Różnica między dwoma porządkami przejścia polega na wyborze
Container
.Jak wygląda rekurencyjna implementacja
Rekurencja kończy się, gdy dojdziesz do węzła, który nie ma dzieci, więc jest gwarantowana dla skończonych, acyklicznych grafów.
W tym momencie nadal trochę oszukiwałem. Przy odrobinie sprytu możesz również pracować nad węzłami w następującej kolejności:
co jest odmianą pierwszej głębi, w której nie wykonuję pracy w każdym węźle, dopóki nie wrócę na drzewo. Jednak odwiedziłem wyższe węzły w drodze w dół, aby znaleźć ich dzieci.
To jest dość naturalne przechodzenie w rekurencyjnym realizacji (użyć wiersza „alternate czas” powyżej zamiast pierwszej linii „Praca”), a nie zbyt trudne, jeśli używasz jawne stos, ale zostawię to jako ćwiczenie.
źródło
A, B, D, C, E, F
- pierwsza prezentowana), infix (D, B, A, E, C, F
- używany do sortowania: dodaj jako drzewo AVL, a następnie przeczytaj infix) lub postfix (D, B, E, F, C, A
prezentowana alternatywa) traversal. Nazwy są podane na podstawie pozycji, w której przetwarzasz root. Należy zauważyć, że wrostek ma sens tylko w przypadku drzew binarnych. @batbrat to są imiona ... biorąc pod uwagę czas odkąd zapytałeś, prawdopodobnie już wiesz.Zrozumienie terminów:
Ten obraz powinien dać ci wyobrażenie o kontekście, w którym używane są słowa szerokość i głębokość .
Przeszukiwanie w głąb:
Algorytm wyszukiwania w głąb działa tak, jakby chciał jak najszybciej oddalić się od punktu początkowego.
Zwykle używa znaku a,
Stack
aby zapamiętać, dokąd ma się udać, gdy osiągnie ślepy zaułek.Zasady, których należy przestrzegać: Wepchnij pierwszy wierzchołek A do
Stack
Kod Java:
Zastosowania : Przeszukiwanie w głąb jest często używane w symulacjach gier (i sytuacji podobnych do gier w świecie rzeczywistym). W typowej grze możesz wybrać jedną z kilku możliwych akcji. Każdy wybór prowadzi do dalszych wyborów, z których każdy prowadzi do dalszych wyborów i tak dalej, do ciągle rozszerzającego się wykresu możliwości w kształcie drzewa.
Przeszukiwanie wszerz:
Queue
.Kod Java:
Zastosowania : Przeszukiwanie wszerz najpierw znajduje wszystkie wierzchołki oddalone o jedną krawędź od punktu początkowego, następnie wszystkie wierzchołki oddalone o dwie krawędzie i tak dalej. Jest to przydatne, jeśli próbujesz znaleźć najkrótszą ścieżkę od początkowego wierzchołka do danego wierzchołka.
Miejmy nadzieję, że to powinno wystarczyć do zrozumienia wyszukiwań wszerz i najpierw w głąb. Do dalszej lektury polecam rozdział Wykresy z doskonałej książki Roberta Lafore'a o strukturach danych.
źródło
Biorąc pod uwagę to drzewo binarne:
Pierwsze przejście szerokości:
przechodzenie przez każdy poziom od lewej do prawej.
„Jestem G, moje dzieci to D i ja, moje wnuki to B, E, H i K, a ich wnuki to A, C, F”
Pierwsze przejście w głąb:
przemierzanie nie jest wykonywane jednocześnie na całych poziomach. Zamiast tego, przemierzanie nurkuje najpierw w GŁĘBOKOŚCI (od korzenia do liścia) drzewa. Jest to jednak nieco bardziej złożone niż po prostu w górę iw dół.
Istnieją trzy metody:
Użycie (aka, dlaczego nas to obchodzi):
bardzo podobało mi się to proste wyjaśnienie Quora dotyczące metod przechodzenia przez głębokość na początku i ich powszechnego stosowania:
„Przechodzenie na zamówienie wypisze wartości [w kolejności dla BST (drzewo wyszukiwania binarnego)] "
" Przechodzenie w przedsprzedaży służy do tworzenia kopii [drzewa wyszukiwania binarnego]. "
„Przechodzenie po zamówieniu służy do usuwania [drzewa wyszukiwania binarnego]”.
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing
źródło
Myślę, że byłoby interesujące napisać oba z nich w taki sposób, że tylko zmiana niektórych linii kodu daje jeden algorytm lub drugi, dzięki czemu zobaczysz, że twój dillema nie jest tak silny, jak się wydaje na początku .
Osobiście podoba mi się interpretacja BFS jako zalewania krajobrazu: najpierw zostaną zalane obszary na niskich wysokościach, a dopiero potem obszary na dużych wysokościach. Jeśli wyobrazisz sobie wysokości krajobrazowe jako izolinie, jakie widzimy w podręcznikach geografii, łatwo zauważyć, że BFS wypełnia cały obszar w tym samym izolinie w tym samym czasie, tak jak w przypadku fizyki. Zatem interpretacja wysokości jako odległości lub skalowanego kosztu daje dość intuicyjne wyobrażenie o algorytmie.
Mając to na uwadze, możesz łatwo dostosować ideę wyszukiwania wszerz, aby łatwo znaleźć minimalne drzewo rozpinające, najkrótszą ścieżkę, a także wiele innych algorytmów minimalizacji.
Nie widziałem jeszcze żadnej intuicyjnej interpretacji DFS (tylko standardowa o labiryncie, ale nie jest tak potężna jak BFS i zalanie), więc wydaje mi się, że BFS wydaje się lepiej korelować ze zjawiskami fizycznymi opisanymi powyżej, podczas gdy DFS lepiej koreluje z wyborami dillema w systemach racjonalnych (np. Ludzie lub komputery decydujące, który ruch wykonać w grze w szachy lub wyjść z labiryntu).
Tak więc dla mnie różnica polega na tym, które zjawisko naturalne najlepiej pasuje do ich modelu propagacji (poprzecznego) w prawdziwym życiu.
źródło