Ancho Primero Vs Profundidad Primero

Al atravesar un árbol / gráfico, ¿cuál es la diferencia entre primero la anchura y la profundidad primero? Cualquier codificación o ejemplo de pseudocódigo sería genial.

Estos dos términos diferencian entre dos formas diferentes de caminar un árbol.

Probablemente sea más fácil exhibir la diferencia. Considera el árbol:

    A
   / \
  B   C
 /   / \
D   E   F

Un primer recorrido profundo visitaría los nodos en este orden

A, B, D, C, E, F

Observe que baja una pierna antes de continuar.

Un primer recorrido ancho visitaría el nodo en este orden

A, B, C, D, E, F

Aquí trabajamos todo el camino a través de cada nivel antes de bajar.

(Tenga en cuenta que existe cierta ambigüedad en las órdenes transversales, y he hecho trampa para mantener el orden de "lectura" en cada nivel del árbol. En cualquier caso, podría llegar a B antes o después de C, y del mismo modo podría llegar a E antes o después de F. Esto puede o no importar, depende de su aplicación ...)

Ambos tipos de recorrido se pueden lograr con el pseudocódigo:

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

La diferencia entre las dos órdenes transversales radica en la elección de Container.

• Para profundidad, primero use una pila. (La implementación recursiva usa la pila de llamadas ...)
• Para amplitud primero use una cola.

La implementación recursiva se parece a

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

La recursión finaliza cuando llega a un nodo que no tiene hijos, por lo que se garantiza que finalizará para gráficos acíclicos finitos.

En este punto, todavía he engañado un poco. Con un poco de inteligencia, también puede trabajar en los nodos en este orden:

D, B, E, F, C, A

que es una variación de profundidad primero, donde no hago el trabajo en cada nodo hasta que estoy caminando de regreso al árbol. Sin embargo, he visitado los nodos superiores en el camino para encontrar a sus hijos.

Este recorrido es bastante natural en la implementación recursiva (use la línea "Tiempo alternativo" arriba en lugar de la primera línea "Trabajo"), y no demasiado difícil si usa una pila explícita, pero lo dejaré como un ejercicio.

Comprensión de los términos:

Esta imagen debería darle una idea sobre el contexto en el que se usan las palabras amplitud y profundidad .

Profundidad-Primera búsqueda:

• El algoritmo de búsqueda de profundidad primero actúa como si quisiera alejarse lo más rápido posible del punto de partida.

• Generalmente usa un Stackpara recordar dónde debe ir cuando llega a un callejón sin salida.

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

  1. Si es posible, visite un vértice no visitado adyacente, márquelo como visitado y empújelo 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 puede seguir la Regla 1 o la Regla 2, ya está.

• 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 : las búsquedas de profundidad primero se utilizan a menudo en simulaciones de juegos (y situaciones similares a juegos en el mundo real). En un juego típico, puedes elegir una de varias acciones posibles. Cada opción conduce a más opciones, cada una de las cuales conduce a más opciones, y así sucesivamente en un gráfico de posibilidades en forma de árbol en constante expansión.

Breadth-First Search:

• Al algoritmo de búsqueda de amplitud le gusta estar lo más cerca posible del punto de partida.
• Este tipo de búsqueda generalmente se implementa usando a Queue.
• Reglas a seguir: Convertir el Vértice A inicial en el vértice actual
  1. Visite el siguiente vértice no visitado (si hay uno) adyacente al vértice actual, márquelo e insértelo en la cola.
  2. Si no puede llevar a cabo la Regla 1 porque ya no hay 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 está vacía, ya está.

• 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;
  }
  

• Aplicaciones : La búsqueda de amplitud primero encuentra primero todos los vértices que están a un borde del punto de partida, luego todos los vértices que están a dos bordes, y así sucesivamente. Esto es útil si está tratando de encontrar la ruta más corta desde el vértice inicial hasta un vértice dado.

Con suerte, eso debería ser suficiente para comprender las búsquedas Breadth-First y Depth-First. Para leer más, recomendaría el capítulo de Gráficos de un excelente libro de estructuras de datos de Robert Lafore.

Dado este árbol binario:

Anchura del primer recorrido :
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 del primer recorrido: el
recorrido no se realiza a través de niveles completos a la vez. En cambio, el recorrido se sumerge primero en la PROFUNDIDAD (desde la raíz hasta la hoja) del árbol. Sin embargo, es un poco más complejo que simplemente subir y bajar.

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 Profundidad de primer recorrido y cómo se usan comúnmente:
"El recorrido en orden imprimirá valores [para el BST (árbol de búsqueda binario)] "
" El recorrido de preorden se utiliza para crear una copia del [árbol de búsqueda binario] ".
"El recorrido posterior al pedido se utiliza para eliminar el [árbol de búsqueda binario]".
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

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 ser al principio .

Personalmente, me gusta la interpretación de BFS como una inundación de un paisaje: las áreas de baja altitud se inundarán primero, y solo entonces las áreas de alta altitud seguirán. Si imagina las altitudes del paisaje como isolinas como vemos en los libros de geografía, es fácil ver que BFS llena todas las áreas bajo la misma isolínea al mismo tiempo, tal como sería con la física. Por lo tanto, interpretar las 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 la primera búsqueda de amplitud para encontrar fácilmente el árbol de expansión mínimo, la ruta más corta y también muchos otros algoritmos de minimización.

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

Entonces, para mí, la diferencia entre mentiras es qué fenómeno natural se adapta mejor a su modelo de propagación (transversal) en la vida real.