Ширину С Глубиной Первой

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

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

---

Глубину Поиска:

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

• он обычно использует 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.
• правила: Сделать стартовой вершины в текущую вершину
  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;
  }
  

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

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

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

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

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

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

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

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

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

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