algorithm - directed - Breadth First Vs Depth First

breadth first search tree java

Question

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

Answer 1

Comprender los términos:

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

Profundidad: primera búsqueda:

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

• Por lo general, utiliza una Stack para recordar dónde debe ir cuando llega a un callejón sin salida.

• Reglas a seguir: presione el primer vértice A en la 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 puede seguir la Regla 1, entonces, si es posible, saque un vértice de la pila.
  3. Si no puede seguir la Regla 1 o la Regla 2, ya ha terminado.

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

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

Búsqueda de primer orden:

• El algoritmo de búsqueda de amplitud le gusta mantenerse lo más cerca posible del punto de partida.
• Este tipo de búsqueda generalmente se implementa utilizando una Queue .
• Reglas a seguir: hacer que el vértice A sea el vértice actual
  1. Visite el siguiente vértice no visitado (si lo hay) 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 está vacía, ya ha terminado.

• 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 primero en primer lugar encuentra primero todos los vértices que están a un borde del punto de inicio, luego todos los vértices que están a dos bordes de distancia, 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.

Afortunadamente, eso debería ser suficiente para comprender las búsquedas Primero primero y Primero profundidad. Para leer más, recomendaría el capítulo Gráficos de un excelente libro de estructuras de datos de Robert Lafore.

Answer 2

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

Personalmente me gusta la interpretación de BFS como 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 imagina 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, al igual que con la física. Por lo tanto, la interpretación de altitudes como la distancia o el 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 ancho 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 poderosa como BFS e inundación), así que para mí parece que BFS parece correlacionarse mejor con los fenómenos físicos que los descritos anteriormente, mientras que DFS se correlaciona mejor con las elecciones dillema en los sistemas racionales (es decir, las personas o las computadoras que deciden qué movimiento hacer en una partida de ajedrez o salir de un laberinto).

Entonces, para mí, la diferencia entre las mentiras sobre qué fenómeno natural coincide mejor con su modelo de propagación (transversal) en la vida real.

Answer 3

Dado este árbol binario:

Breadth First Traversal:
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 de primer recorrido:
La travesía no se realiza a TRAVÉS de niveles enteros a la vez. En cambio, el recorrido se sumerge en la PROFUNDIDAD (de la raíz a la hoja) del árbol primero. 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 en primer cruce y cómo se usan comúnmente:
"In-Order Traversal imprimirá valores [para el BST (árbol de búsqueda binaria)]"
"El recorrido previo al pedido se usa para crear una copia del [árbol de búsqueda binario]".
"El recorrido posterior al pedido se usa 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

Answer 4

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

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

    A
   / /
  B   C
 /   / /
D   E   F

Un primer recorrido de profundidad visitaría los nodos en este orden

A, B, D, C, E, F

Observe que baja hasta 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 hay cierta ambigüedad en las órdenes de cruce, 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 uso en amplitud primero use una cola.

La implementación recursiva parece

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 se 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 hecho trampas 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 la profundidad en primer lugar, 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 hacia abajo para encontrar a sus hijos.

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