Anchura Primero Vs Profundidad Primero

Entendiendo los términos:

Esta imagen debería darte una idea del contexto en el que se usan las palabras width y depth.

Búsqueda en profundidad:

• El algoritmo de búsqueda en profundidad actúa como si quisiera llegar lo más lejos posible desde el punto de partida lo más rápido posible.

• Generalmente utiliza un Stack para recordar a dónde debe ir cuando llega a un callejón sin salida.

• Reglas a seguir: Empuje el primer vértice A en el Stack

  1. Si es posible, visite un vértice adyacente no visitado, márquelo como visitado y púlselo en la pila.
  2. Si no puedes seguir la Regla 1, entonces, si es posible, saca un vértice de la pila.
  3. Si no puedes seguir la Regla 1 o la Regla 2, estás acabado.

• Código 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;
  }
  

• Aplicaciones: A menudo se utilizan búsquedas en profundidad en simulaciones de juegos (y situaciones similares a juegos en el mundo real). En un juego típico se puede elegir una de varias acciones posibles. Cada elección conduce a más elecciones, cada una de las cuales conduce a más elecciones, y así sucesivamente en un gráfico de posibilidades en forma de árbol en constante expansión.

Búsqueda primero en anchura:

• Al algoritmo de búsqueda primero en amplitud le gusta mantenerse lo más cerca posible al punto de partida.
• Esto el tipo de búsqueda se implementa generalmente usando un Queue.
• Reglas a seguir: Convierte el Vértice inicial en el vértice actual
  1. Visite el siguiente vértice no visitado (si hay uno) que está adyacente al vértice actual, márquelo e insértelo en la cola.
  2. Si no puede llevar a cabo la Regla 1 porque no hay más vértices no visitados, elimine un vértice de la cola (si es posible) y conviértalo en el vértice actual.
  3. Si no puede llevar a cabo la Regla 2 porque la cola es vacío, estás acabado.

• Código 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;
  }
  

• Applications : La búsqueda de amplitud primero encuentra todos los vértices que están a una arista del punto de partida, luego todos los vértices que están a dos aristas de distancia, y así sucesivamente. Esto es útil si está tratando de encontrar el camino más corto desde el vértice inicial hasta un vértice dado.

Esperemos que eso sea suficiente para entender las búsquedas de Amplitud y Profundidad. Para leer más, recomendaría el capítulo de Gráficos de un excelente libro de estructuras de datos de Robert Lafore.

Creo que sería interesante escribir ambos de una manera que solo cambiando algunas líneas de código le daría un algoritmo u otro, para que vea que su dillema no es tan fuerte como parece al principio.

Personalmente me gusta la interpretación de BFS como la inundación de un paisaje: las áreas de baja altitud se inundarán primero, y solo entonces las áreas de gran altitud seguirían. Si imaginas las altitudes del paisaje como isolíneas como vemos en los libros de geografía, es fácil ver que BFS llena todo el área bajo la misma isolínea al mismo tiempo, como esto sería con la física. Por lo tanto, interpretar altitudes como distancia o costo escalado da una idea bastante intuitiva del algoritmo.

Con esto en mente, puede adaptar fácilmente la idea detrás de breadth first search para encontrar el árbol de expansión mínimo fácilmente, el camino más corto y también muchos otros algoritmos de minimización.

Todavía no he visto ninguna interpretación intuitiva de DFS (solo la estándar sobre el laberinto, pero no es tan poderoso como el BFS y las inundaciones), por lo que para mí parece que BFS parece correlacionarse mejor con los fenómenos físicos como se describe anteriormente, mientras que DFS se correlaciona mejor con las elecciones dillema en sistemas racionales (es decir, personas o computadoras que deciden qué movimiento hacer en una partida de ajedrez o salir de un laberinto).

Por lo tanto, para mí la diferencia entre radica en qué fenómeno natural coincide mejor con su modelo de propagación (transversal) en la vida real.

Dado este árbol binario:

Anchura Primera Travesía:
Atraviesa cada nivel de izquierda a derecha.

"Soy G, mis hijos son D y yo, mis nietos son B, E, H y K, sus nietos son 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

Profundidad Primera Travesía:
El recorrido no se realiza a través de niveles enteros a la vez. En su lugar, traversal se sumerge primero en la PROFUNDIDAD (de la raíz a la hoja) del árbol. Sin embargo, es un poco más complejo que simplemente arriba y abajo.

Hay tres métodos:

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

Uso (también conocido como, ¿por qué nos importa):
Realmente disfruté esta explicación simple de Quora de los métodos de Primer Recorrido de Profundidad y cómo se usan comúnmente:
"El recorrido en orden imprimirá valores [en orden para el BST (árbol de búsqueda binaria)]"
"Pre-order traversal se utiliza para crear una copia del [árbol de búsqueda binario]."
"Postorder traversal se utiliza para eliminar la [búsqueda binaria tree]."
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing