Сначала в ширину против сначала в глубину

Эти два термина различают два разных способа ходьбы по дереву.

Наверное, проще всего показать разницу. Рассмотрим дерево:

    A
   / \
  B   C
 /   / \
D   E   F

При первом обходе глубины узлы будут посещаться в этом порядке.

A, B, D, C, E, F

Обратите внимание, что вы полностью опускаетесь на одну ногу, прежде чем двигаться дальше.

При первом обходе ширины узел будет посещаться в этом порядке.

A, B, C, D, E, F

Здесь мы проходим полностью через каждый уровень, прежде чем спускаться вниз.

(Обратите внимание, что есть некоторая двусмысленность в порядках обхода, и я обманул, чтобы поддерживать порядок "чтения" на каждом уровне дерева. В любом случае я мог бы добраться до B до или после C, и аналогичным образом я мог бы добраться до E до или после F. Это может иметь значение, а может и не иметь значения, зависит от вашего приложения ...)

Оба вида обхода могут быть выполнены с помощью псевдокода:

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

Разница между двумя порядками обхода заключается в выборе Container.

• Для параметра сначала глубина используйте стопку. (Рекурсивная реализация использует стек вызовов ...)
• Для в ширину используйте очередь.

Рекурсивная реализация выглядит как

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

Рекурсия заканчивается, когда вы достигаете узла, у которого нет дочерних элементов, поэтому для конечных ациклических графов она гарантированно завершится.

На данный момент я еще немного схитрил. Проявив немного смекалки, вы также можете поработать над узлами в следующем порядке:

D, B, E, F, C, A

это разновидность метода «сначала глубина», когда я не выполняю работу на каждом узле, пока не вернусь обратно вверх по дереву. Однако я посетил верхние узлы на пути вниз, чтобы найти их детей.

Этот обход довольно естественен в рекурсивной реализации (используйте строку «Альтернативное время» выше вместо первой строки «Работа») и не слишком, если вы используете явный стек, но я оставь это как упражнение.

Понимание терминов:

Это изображение должно дать вам представление о контексте, в котором используются слова ширина и глубина.

Поиск в глубину:

• Алгоритм поиска в глубину действует так, как если бы он хотел как можно быстрее уйти как можно дальше от начальной точки.

• Обычно он использует Stack, чтобы запомнить, куда он должен идти, когда заходит в тупик.

• Правила, которым нужно следовать: надавите на первую вершину A на Stack

  1. If possible, visit an adjacent unvisited vertex, mark it as visited, and push it on the stack.
  2. Если вы не можете следовать Правилу 1, по возможности извлеките вершину из стека.
  3. Если вы не можете следовать Правилу 1 или Правилу 2, все готово.

• Код 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;
  }
  

• Приложения: поиск в глубину часто используется при моделировании игр (и игровых ситуаций в реальном мире). В обычной игре вы можете выбрать одно из нескольких возможных действий. Каждый выбор ведет к дальнейшему выбору, каждый из которого ведет к дальнейшему выбору, и так далее до постоянно расширяющегося древовидного графа возможностей.

Поиск в ширину:

• Алгоритм поиска в ширину предпочитает оставаться как можно ближе к начальной точке.
• Такой поиск обычно реализуется с использованием Queue.
• Rules to follow: Make starting Vertex A the current vertex
  1. Visit the next unvisited vertex (if there is one) that’s adjacent to the current vertex, mark it, and insert it into the queue.
  2. Если вы не можете выполнить Правило 1, потому что больше нет непосещенных вершин, удалите вершину из очереди (если возможно) и сделайте ее текущей вершиной.
  3. Если вы не можете выполнить Правило 2, потому что очередь пуста, все готово.

• Код 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;
  }
  

• Приложения: поиск в ширину сначала находит все вершины, которые находятся на расстоянии одного ребра от начальной точки, а затем все вершины, которые находятся на расстоянии двух краев и т. д. Это полезно, если вы пытаетесь найти кратчайший путь от начальной вершины до данной вершины.

Надеюсь, этого должно быть достаточно для понимания поисковых запросов в ширину и в глубину. Для дальнейшего чтения я бы порекомендовал главу «Графики» из прекрасной книги Роберта Лафора о структурах данных.

Учитывая это двоичное дерево:

Обход в ширину:
Пересекайте каждый уровень слева направо.

"Я G, мои дети D и я, мои внуки B, E, H и K, их внуки 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

Обход по глубине:
Обход не выполняется ПОСЕЧНО целыми уровнями за раз. Вместо этого обход сначала погружается в ГЛУБИНУ (от корня к листу) дерева. Однако это немного сложнее, чем просто вверх и вниз.

Есть три метода:

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

Использование (также известное как нас волнует):
Мне очень понравилось это простое объяснение Quora методов обхода глубины и того, как они обычно используются:
«Обход по порядку будет напечатан значения [для BST (двоичного дерева поиска)] "
" Предварительный обход используется для создания копии [двоичного дерева поиска]. "
" Последующий обход используется для удаления [двоичного дерево поиска]. "
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

Я думаю, было бы интересно написать их так, чтобы только переключение нескольких строк кода давало вам тот или иной алгоритм, чтобы вы увидели, что ваша диллема не так сильна, как кажется на первый взгляд. .

Мне лично нравится интерпретация BFS как затопления ландшафта: сначала будут затоплены малые высотные районы, а уже потом - высокогорные. Если вы представите высоту ландшафта в виде изолиний, как мы видим в книгах по географии, легко увидеть, что BFS заполняет всю область под одной и той же изолинией одновременно, как это было бы с физикой. Таким образом, интерпретация высоты как расстояния или масштабированной стоимости дает довольно интуитивное представление об алгоритме.

Имея это в виду, вы можете легко адаптировать идею поиска в ширину, чтобы легко найти минимальное остовное дерево, кратчайший путь, а также многие другие алгоритмы минимизации.

Я пока не видел какой-либо интуитивной интерпретации DFS (только стандартная для лабиринта, но она не такая мощная, как BFS и наводнение), поэтому мне кажется, что BFS, кажется, лучше коррелирует с физическими явлениями, как описано выше, в то время как DFS лучше коррелирует с дилеммой выбора рациональных систем (т. Е. Люди или компьютеры решают, какой ход сделать в шахматной партии или выйти из лабиринта).

Итак, для меня разница между тем, какое природное явление лучше всего соответствует их модели распространения (пересечения) в реальной жизни.