Ширина первая против глубины первая

Question

При обходе дерева / графика, в чем разница между шириной первой и глубиной первой? Любые примеры кодирования или псевдокода были бы хороши.

Answer 1

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

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

    A
   / \
  B   C
 /   / \
D   E   F

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

A, B, D, C, E, F

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

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

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

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

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

Answer 2

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

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

---

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

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

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

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

  1. Если возможно, посетите соседнюю не посещенную вершину, отметьте ее как посещенную и поместите в стек.
  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.
• Правила, которым нужно следовать: сделать начальную вершину A текущей вершиной
  1. Посетите следующую не посещенную вершину (если она есть), которая находится рядом с текущей вершиной, отметьте ее и вставьте в очередь.
  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;
  }
  

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

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

Answer 3

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

Ширина первого обхода:
Пройдите через каждый уровень слева направо.

«Я 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 методов глубинного обхода и того, как они обычно используются:
«In-Order Traversal напечатает значения [в порядке BST (дерево двоичного поиска)]»
«Обход предварительного заказа используется для создания копии [дерева двоичного поиска].»
Msgstr "Обратный путь по порядку используется для удаления [бинарного дерева поиска]." https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

Answer 4

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

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

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

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

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