Ancho Primero Vs Profundidad Primero

172

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.

Ted Smith
fuente
66
¿Revisaste Wikipedia ( profundidad primero , ancho primero )? Hay ejemplos de código en esas páginas, junto con muchas imágenes bonitas.
rmeador
Tuve ese pensamiento también, pero entonces los ejemplos dados son un poco mejor que las que se encuentran en la wikipedia ....
jonnybazookatone

Respuestas:

292

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.

dmckee --- gatito ex moderador
fuente
@dmckee ¡Gracias! Creo que quisiste decir "Trabajar en la carga útil en Node", ¿verdad?
Batbrat
44
Vale la pena señalar que puede modificar la versión de profundidad primero para obtener el prefijo ( A, B, D, C, E, F- el primero presentado), infijo ( D, B, A, E, C, F- usado para la clasificación: agregar como un árbol AVL y luego leer infijo) o postfix ( D, B, E, F, C, Ala alternativa presentada) transversal. Los nombres están dados por la posición en la que procesa la raíz. Cabe señalar que infix solo tiene sentido para árboles binarios. @batbrat esos son los nombres ... dado el tiempo desde que lo preguntaste, probablemente ya lo sepas.
Theraot 01 de
@Theraot gracias por agregar eso! Sí, sé acerca de este tipo de recorridos y por qué Infix tiene sentido solo para árboles binarios.
Batbrat
¿Cómo decidir qué solución tiene una mejor complejidad de espacio o tiempo?
IgorGanapolsky
1
@IgorGanapolsky Debería ser el mismo para ambos por principio (después de todo, usan esencialmente el mismo código). Una pregunta más interesante sería cómo impactan el caché y el conjunto de trabajo, pero creo que eso dependerá de la morfología del árbol.
dmckee --- ex-gatito moderador
95

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 .

Comprender la amplitud y la profundidad


Profundidad-Primera búsqueda:

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:

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.

Yogesh Umesh Vaity
fuente
66
Si tuviera diez votos más, lo haría.
snr
@snr podrías otorgar una recompensa;)
Snow
@Snow, si le dices a sus directivas, puedo hacerlo. No se como hacerlo.
snr
Gracias @snr, estoy muy contento de recibir mi primera recompensa. Lo aprecio mucho.
Yogesh Umesh Vaity
1
Gracias @Snow, me alegra que hayan encontrado útil mi respuesta.
Yogesh Umesh Vaity
4

Dado este árbol binario:

ingrese la descripción de la imagen aquí

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

msyinmei
fuente
2

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.

usuario5193682
fuente
1
Puede implementarlos con un algoritmo similar, solo use stack para DFS y cola para BFS. El problema con BFS es que necesita realizar un seguimiento de todos los nodos vistos hasta ahora. DFS en física ... Me imagino universos alternativos y quieres uno con vida, todos hijos de raíz, son diferentes big bangs y vas hasta la muerte del universo, ¿no hay vida? vuelves a la última bifurcación e intentas otro turno, hasta que todos se agoten y pases al siguiente big bang, estableciendo nuevas leyes físicas para el nuevo universo. super intuitivo Un buen problema es encontrar un camino con el caballo en un tablero de ajedrez.
juanmf