En primer lugar amplitud Vs Profundidad Primero

StackOverflow https://stackoverflow.com/questions/687731

Pregunta

Cuando recorrer un árbol / gráfico cuál es la diferencia entre la amplitud y profundidad de Primera primero? Cualquier ejemplo de codificación o pseudocódigo sería grande.

¿Fue útil?

Solución

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

Es probablemente más fácil sólo para exhibir la diferencia. Considere el árbol: 

    A
   / \
  B   C
 /   / \
D   E   F

A profundidad primero traversal volvería de los nodos en este orden 

A, B, D, C, E, F

Tenga en cuenta que usted va todo el camino por una pierna antes de continuar.

anchura primer recorrido sería visitar 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 una cierta ambigüedad en las órdenes de recorrido, y he engañado para mantener el orden "leer" en cada nivel del árbol. En cualquiera de los casos podría conseguir a B antes o después de C, y del mismo modo que podría llegar a E antes o después de F. Esto puede o puede no importar, que depende de la aplicación ...)

Los dos tipos de recorrido se puede 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 los dos órdenes de recorrido reside en la elección de Container.

  • En profundidad primero utilizar una pila. (La implementación recursiva utiliza la pila de llamadas ...)
  • En primero en amplitud utilizar 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 termina cuando se llega a un nodo que no tiene hijos, por lo que está garantizado para terminar de finita, acíclicos gráficos.

En este punto, todavía tengo una pequeña trampa. Con un poco de inteligencia también se puede trabajo en los nodos en este orden: 

D, B, E, F, C, A

que es una variación del primero en profundidad, en la que no hago el trabajo en cada nodo hasta que estoy caminando hacia atrás encima del árbol. sin embargo tengo visitada los nodos más altos en el camino para encontrar a sus hijos.

Este recorrido es bastante natural en la implementación recursiva (utilizar la línea "tiempo alternativo" por encima en lugar de la primera línea de "trabajo"), y no también difícil si se utiliza una pila explícita, pero lo dejo como ejercicio.

Otros consejos

La comprensión de los términos:

Esta imagen que debe dar la idea acerca del contexto en el que las palabras anchura y profundidad se utiliza.

Amplitud y profundidad entendimiento

Profundidad-primera búsqueda:

Profundidad-First Search

  • Profundidad-primer algoritmo de búsqueda actúa como si se quiere llegar lo más lejos desde el punto de partida lo más rápidamente posible.

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

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

    1. Si es posible, visite a un vértice no visitado adyacente, marcarlo como visitó, y empuje en la pila.
    2. Si usted no puede seguir la Regla 1, y luego, si es posible, hacer estallar un vértice de la pila.
    3. Si usted no puede seguir la regla 1 ó 2, ya está hecho.

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

  • : Búsquedas primero en profundidad se utilizan a menudo en las simulaciones de juegos (y situaciones de juego como en el mundo real). En un típico juego se puede elegir una de varias acciones posibles. Cada opción da lugar a nuevas opciones, cada una de las cuales conduce a más opciones, y así sucesivamente en un gráfico en forma de árbol cada vez mayor de posibilidades.

Búsqueda primero en amplitud:

Búsqueda primero en amplitud

  • El algoritmo de búsqueda primero en amplitud le gusta estar lo más cerca posible al punto de partida.
  • Este tipo de búsqueda se lleva a cabo generalmente usando un Queue.
  • Reglas a seguir: Hacer comenzando El vértice A del vértice actual
    1. Visita el siguiente vértice unvisited (si hay uno) que es adyacente al vértice actual, marcarlo, y la inserta en la cola.
    2. Si no puede llevar a cabo la Regla 1, porque ya no hay vértices más visitados, eliminar un vértice de la cola (si es posible) y que sea el vértice actual.
    3. Si no puede llevar a cabo la Regla 2, ya que 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;
}

  • : primero en amplitud búsqueda encuentra en primer lugar todos los vértices que son uno de los bordes de distancia desde el punto de partida , a continuación, todos los vértices que son dos bordes de distancia, y así sucesivamente. Esto es útil si usted está tratando de encontrar el camino más corto desde el vértice a partir de un vértice dado.

Con suerte eso debería ser suficiente para comprender el primero en amplitud y busca primero en profundidad. Para leer más, le recomendaría el capítulo gráficos a partir de un libro excelente estructuras de datos por Robert Lafore.

Dado este árbol binario:

introducir descripción de la imagen aquí

Amplitud Primera Transversal:
Traverse través de cada nivel de izquierda a derecha.

"Soy G, mis hijos son D e I, 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 Transversal:
Transversal no se realiza dentro de los diferentes enteras a la vez. En su lugar, el recorrido se sumerge en la profundidad (desde la raíz hasta las hojas) del árbol en primer lugar. 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 interesa):
Me gustó mucho esta explicación simple Quora de la profundidad métodos Primera Transversales y la forma en que se utilizan comúnmente:
"Dentro de la orden de recorrido imprimirá valores [Para que la BST (árbol binario de búsqueda)]"
"Pre-orden transversal se utiliza para crear una copia de la [árbol binario de búsqueda]."
"Orden posterior recorrido se utiliza para eliminar la [árbol binario de búsqueda]."
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 tanto de ellos de una manera que únicamente conectando de algunas líneas de código que le daría un algoritmo o la otra, por lo que se verá que su dillema no es tan fuerte como parece ser al primero.

Personalmente, me gusta la interpretación de BFS como la inundación de un paisaje: las zonas de baja altitud se inundarán primero, y sólo entonces seguirían las zonas de gran altitud. Si usted se imagina las alturas del paisaje en forma de 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 esto sería con la física. Por lo tanto, la interpretación de altitudes como la distancia o coste reducido da una idea bastante intuitiva del algoritmo.

Con esto en mente, puede adaptar fácilmente la idea detrás de búsqueda en anchura para encontrar el árbol de expansión mínimo con facilidad, la ruta más corta, y también muchos otros algoritmos de minimización.

No he visto ninguna interpretación intuitiva de DFS todavía (sólo el estándar sobre el laberinto, pero ¿no es cierto tan poderoso como el BFS uno e inundaciones), así que para mí parece que BFS parece correlacionarse mejor con los fenómenos físicos como se describe anterior, mientras que DFS se correlaciona mejor con opciones dillema en sistemas racionales (es decir, personas o equipos que deciden que se mueven para hacer en un juego de ajedrez o salir de un laberinto).

Así que, para mí la diferencia entre la mentira en la que fenómeno natural mejor coincide con el modelo de propagación (transversing) en la vida real.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top