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

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.

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.

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

• 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.

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”

- 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

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.