Najpierw szerokość a najpierw głębokość

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.

Ted Smith
źródło
6
Czy sprawdzić Wikipedię ( głębokość pierwszy , szerokość pierwszy )? Na tych stronach znajdują się przykłady kodu wraz z wieloma ładnymi obrazkami.
rmeador
Myślałem o tym, ale podane przykłady są nieco ładniejsze niż te znalezione na wikipedii ....
jonnybazookatone

Odpowiedzi:

291

Te dwa terminy rozróżniają dwa różne sposoby chodzenia po drzewie.

Najłatwiej jest chyba pokazać różnicę. Rozważ drzewo:

    A
   / \
  B   C
 /   / \
D   E   F

Głębokość pierwszy przejścia odwiedzi węzły w tej kolejności

A, B, D, C, E, F

Zwróć uwagę, że przed przejściem dalej schodzisz całą nogę w dół .

Szerokość pierwszy przejścia odwiedzi węzeł w tej kolejności

A, B, C, D, E, F

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:

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

Różnica między dwoma porządkami przejścia polega na wyborze Container.

  • Aby uzyskać głębokość, najpierw użyj stosu. (Implementacja rekurencyjna używa stosu wywołań ...)
  • Aby uzyskać szerokość, najpierw użyj kolejki.

Jak wygląda rekurencyjna implementacja

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

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:

D, B, E, F, C, A

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.

dmckee --- kociak ex-moderator
źródło
@dmckee Thanks! Myślę, że miałeś na myśli „Pracuj nad ładunkiem w Node”, prawda?
batbrat
4
Warto zauważyć, że możesz zmodyfikować wersję z pierwszą głębią, aby uzyskać prefiks ( 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, Aprezentowana 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.
Theraot
@Theraot dzięki za dodanie tego! Tak, wiem o tego rodzaju przemierzaniach i dlaczego wrostek ma sens tylko w przypadku drzew binarnych.
batbrat
Jak zdecydować, które rozwiązanie ma lepszą złożoność przestrzenną lub czasową?
Igor Ganapolsky
1
@IgorGanapolsky Powinien być taki sam dla obu z zasady (w końcu używają zasadniczo tego samego kodu). Bardziej interesującym pytaniem byłoby, jak wpływają one na pamięć podręczną i zestaw roboczy, ale myślę, że będzie to zależeć od morfologii drzewa.
dmckee --- kociak ex-moderator
95

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ść .

Zrozumienie szerokości i głębokości


Przeszukiwanie w głąb:

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, Stackaby 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

    1. Jeśli to możliwe, odwiedź sąsiedni nieodwiedzony wierzchołek, oznacz go jako odwiedzony i wepchnij na stos.
    2. Jeśli nie możesz postępować zgodnie z regułą 1, jeśli to możliwe, zdejmij wierzchołek ze stosu.
    3. Jeśli nie możesz zastosować się do reguły 1 lub reguły 2, to wszystko.
  • Kod Java:

    public void searchDepthFirst() {
        // Begin at vertex 0 (A)
        vertexList[0].wasVisited = true;
        displayVertex(0);
        stack.push(0);
        while (!stack.isEmpty()) {
            int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
            // If no such vertex
            if (adjacentVertex == -1) {
                stack.pop();
            } else {
                vertexList[adjacentVertex].wasVisited = true;
                // Do something
                stack.push(adjacentVertex);
            }
        }
        // Stack is empty, so we're done, reset flags
        for (int j = 0; j < nVerts; j++)
            vertexList[j].wasVisited = false;
    }
    
  • 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:

Przeszukiwanie wszerz

  • Algorytm przeszukiwania wszerz lubi pozostać jak najbliżej punktu startowego.
  • Ten rodzaj wyszukiwania jest zwykle implementowany przy użyciu rozszerzenia Queue.
  • Zasady do przestrzegania: Uczyń początkowy wierzchołek A bieżącym wierzchołkiem
    1. Odwiedź następny nieodwiedzony wierzchołek (jeśli taki istnieje), który sąsiaduje z bieżącym wierzchołkiem, zaznacz go i wstaw do kolejki.
    2. Jeśli nie możesz wykonać reguły 1, ponieważ nie ma już nieodwiedzonych wierzchołków, usuń wierzchołek z kolejki (jeśli to możliwe) i ustaw go jako bieżący wierzchołek.
    3. Jeśli nie możesz zastosować reguły 2, ponieważ kolejka jest pusta, to wszystko.
  • Kod Java:

    public void searchBreadthFirst() {
        vertexList[0].wasVisited = true;
        displayVertex(0);
        queue.insert(0);
        int v2;
        while (!queue.isEmpty()) {
            int v1 = queue.remove();
            // Until it has no unvisited neighbors, get one
            while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
                vertexList[v2].wasVisited = true;
                // Do something
                queue.insert(v2);
            }
        }
        // Queue is empty, so we're done, reset flags
        for (int j = 0; j < nVerts; j++) 
            vertexList[j].wasVisited = false;
    }
    
  • 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.

Yogesh Umesh Vaity
źródło
6
Gdybym miał jeszcze dziesięć praw do oddania głosów, zrobiłbym to.
snr
@snr możesz przyznać nagrodę;)
Snow
@ Teraz, jeśli powiesz jej dyrektywy, mogę. Nie wiem jak to zrobić.
snr
Dziękuję @snr, bardzo się cieszę, że otrzymałem pierwszą nagrodę. Bardzo doceniam.
Yogesh Umesh Vaity
1
Dzięki @Snow, cieszę się, że moja odpowiedź okazała się przydatna.
Yogesh Umesh Vaity
4

Biorąc pod uwagę to drzewo binarne:

wprowadź opis obrazu tutaj

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”

- Level 1: G 
- Level 2: D, I 
- Level 3: B, E, H, K 
- Level 4: A, C, F

Order Searched: G, D, I, B, E, H, K, 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:

1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:  
Grab the Root. (G)  
Then Check the Left. (It's a tree)  
Grab the Root of the Left. (D)  
Then Check the Left of D. (It's a tree)  
Grab the Root of the Left (B)  
Then Check the Left of B. (A)  
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)  
Check the Right of D. (It's a tree)  
Grab the Root. (E)  
Check the Left of E. (Nothing)  
Check the Right of E. (F, Finish D Tree. Move back to G Tree)  
Check the Right of G. (It's a tree)  
Grab the Root of I Tree. (I)  
Check the Left. (H, it's a leaf.)  
Check the Right. (K, it's a leaf. Finish G tree)  
DONE: G, D, B, A, C, E, F, I, H, K  

2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.  
Check the Left of the G Tree. (It's a D Tree)  
Check the Left of the D Tree. (It's a B Tree)  
Check the Left of the B Tree. (A)  
Check the Root of the B Tree (B)  
Check the Right of the B Tree (C, finished B Tree!)  
Check the Right of the D Tree (It's a E Tree)  
Check the Left of the E Tree. (Nothing)  
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...  
Onwards until...   
DONE: A, B, C, D, E, F, G, H, I, K  

3) POSTORDER: 
LEFT, RIGHT, ROOT  
DONE: A, C, B, F, E, D, H, K, I, G

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

msyinmei
źródło
2

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.

user5193682
źródło
1
Możesz je zaimplementować za pomocą podobnego algorytmu, po prostu użyj stosu dla DFS i kolejki dla BFS. Problem z BFS polega na tym, że musisz śledzić wszystkie dotychczas widoczne węzły. DFS w fizyce .. Wyobrażam sobie alternatywne wszechświaty i chcesz jednego z życiem, wszystkie dzieci korzeni, to różne wielkie wybuchy i zejdziesz aż do śmierci wszechświata, żadnego życia? wracasz do ostatniego rozwidlenia i próbujesz kolejnego skrętu, aż wszyscy są wyczerpani i przechodzisz do następnego wielkiego wybuchu, ustalając nowe prawa fizyczne dla nowego wszechświata. super intuicyjny. dobrym problemem jest znalezienie drogi z koniem na szachownicy.
juanmf