Antes de ver las diferencias entre BFS y DFS, primero debemos conocer BFS y DFS por separado.

¿Qué es BFS?

BFS representa Primera búsqueda en amplitud . También se le conoce como recorrido de orden de nivel . La estructura de datos de cola se utiliza para el recorrido de búsqueda primero en amplitud. Cuando utilizamos el algoritmo BFS para recorrer un gráfico, podemos considerar cualquier nodo como un nodo raíz.

Consideremos el siguiente gráfico para el primer recorrido de búsqueda en amplitud.

gimp eliminar marca de agua

Supongamos que consideramos el nodo 0 como un nodo raíz. Por lo tanto, el recorrido se iniciaría desde el nodo 0.

Una vez que el nodo 0 se elimina de la cola, se imprime y se marca como nodo visitado.

Una vez que el nodo 0 se elimina de la cola, los nodos adyacentes del nodo 0 se insertarán en una cola como se muestra a continuación:

Ahora el nodo 1 será eliminado de la cola; se imprime y se marca como un nodo visitado

Una vez que el nodo 1 se elimina de la cola, todos los nodos adyacentes de un nodo 1 se agregarán a una cola. Los nodos adyacentes al nodo 1 son 0, 3, 2, 6 y 5. Pero solo tenemos que insertar nodos no visitados en una cola. Dado que los nodos 3, 2, 6 y 5 no son visitados; por lo tanto, estos nodos se agregarán en una cola como se muestra a continuación:

El siguiente nodo es el 3 en una cola. Entonces, el nodo 3 se eliminará de la cola, se imprimirá y se marcará como visitado como se muestra a continuación:

Una vez que el nodo 3 se elimina de la cola, todos los nodos adyacentes del nodo 3, excepto los nodos visitados, se agregarán a una cola. Los nodos adyacentes al nodo 3 son 0, 1, 2 y 4. Dado que los nodos 0, 1 ya están visitados y el nodo 2 está presente en una cola; por lo tanto, necesitamos insertar solo el nodo 4 en una cola.

nueva línea de Python

Ahora, el siguiente nodo en la cola es 2. Por lo tanto, 2 se eliminaría de la cola. Se imprime y marca como visitado como se muestra a continuación:

Una vez que el nodo 2 se elimina de la cola, todos los nodos adyacentes del nodo 2, excepto los nodos visitados, se agregarán a una cola. Los nodos adyacentes al nodo 2 son 1, 3, 5, 6 y 4. Dado que los nodos 1 y 3 ya han sido visitados, y 4, 5, 6 ya están agregados en la cola; por lo tanto, no necesitamos insertar ningún nodo en la Cola.

El siguiente elemento es 5. Por lo tanto, 5 se eliminaría de la cola. Se imprime y marca como visitado como se muestra a continuación:

Una vez que el nodo 5 se elimina de la cola, todos los nodos adyacentes al nodo 5, excepto los nodos visitados, se agregarán a la cola. Los nodos adyacentes al nodo 5 son 1 y 2. Dado que ambos nodos ya han sido visitados; por lo tanto, no hay ningún vértice para insertar en una cola.

El siguiente nodo es 6. Por lo tanto, 6 se eliminaría de la cola. Se imprime y marca como visitado como se muestra a continuación:

Una vez que el nodo 6 se elimina de la cola, todos los nodos adyacentes al nodo 6, excepto los nodos visitados, se agregarán a la cola. Los nodos adyacentes al nodo 6 son 1 y 4. Dado que el nodo 1 ya ha sido visitado y el nodo 4 ya está agregado a la cola; por lo tanto, no hay ningún vértice para insertar en la Cola.

El siguiente elemento de la cola es 4. Por lo tanto, 4 se eliminaría de la cola. Se imprime y se marca como visitado.

Una vez que el nodo 4 se elimina de la cola, todos los nodos adyacentes al nodo 4, excepto los nodos visitados, se agregarán a la cola. Los nodos adyacentes del nodo 4 son 3, 2 y 6. Dado que todos los nodos adyacentes ya han sido visitados; por lo tanto, no hay ningún vértice para insertar en la cola.

¿Qué es DFS?

DFS significa búsqueda en profundidad primero. En el recorrido DFS, se utiliza la estructura de datos de la pila, que funciona según el principio LIFO (Last In First Out). En DFS, el recorrido se puede iniciar desde cualquier nodo, o podemos decir que cualquier nodo puede considerarse como un nodo raíz hasta que el nodo raíz no se mencione en el problema.

En el caso de BFS, el elemento que se elimina de la cola, los nodos adyacentes al nodo eliminado se agregan a la cola. Por el contrario, en DFS, el elemento que se elimina de la pila, solo un nodo adyacente de un nodo eliminado se agrega a la pila.

Consideremos el siguiente gráfico para el recorrido de búsqueda en profundidad primero.

peso de kat timpf

Considere el nodo 0 como un nodo raíz.

escáner.siguiente java

Primero, insertamos el elemento 0 en la pila como se muestra a continuación:

El nodo 0 tiene dos nodos adyacentes, es decir, 1 y 3. Ahora solo podemos tomar un nodo adyacente, ya sea 1 o 3, para atravesar. Supongamos que consideramos el nodo 1; por lo tanto, se inserta 1 en una pila y se imprime como se muestra a continuación:

Ahora veremos los vértices adyacentes del nodo 1. Los vértices adyacentes no visitados del nodo 1 son 3, 2, 5 y 6. Podemos considerar cualquiera de estos cuatro vértices. Supongamos que tomamos el nodo 3 y lo insertamos en la pila como se muestra a continuación:

Considere los vértices adyacentes no visitados del nodo 3. Los vértices adyacentes no visitados del nodo 3 son 2 y 4. Podemos tomar cualquiera de los vértices, es decir, 2 o 4. Supongamos que tomamos el vértice 2 y lo insertamos en la pila como se muestra a continuación:

Los vértices adyacentes no visitados del nodo 2 son 5 y 4. Podemos elegir cualquiera de los vértices, es decir, 5 o 4. Supongamos que tomamos el vértice 4 y lo insertamos en la pila como se muestra a continuación:

Ahora consideraremos los vértices adyacentes no visitados del nodo 4. El vértice adyacente no visitado del nodo 4 es el nodo 6. Por lo tanto, el elemento 6 se inserta en la pila como se muestra a continuación:

Después de insertar el elemento 6 en la pila, veremos los vértices adyacentes no visitados del nodo 6. Como no hay vértices adyacentes no visitados del nodo 6, no podemos movernos más allá del nodo 6. En este caso, realizaremos retroceder . El elemento superior, es decir, 6, aparecerá de la pila como se muestra a continuación:

El elemento superior de la pila es 4. Dado que no quedan vértices adyacentes no visitados del nodo 4; por lo tanto, el nodo 4 sale de la pila como se muestra a continuación:

El siguiente elemento superior en la pila es 2. Ahora, veremos los vértices adyacentes no visitados del nodo 2. Dado que solo queda un nodo no visitado, es decir, 5, el nodo 5 se empujará a la pila encima de 2 y se imprimirá. Como se muestra abajo:

Ahora comprobaremos los vértices adyacentes del nodo 5, que aún no están visitados. Como no queda ningún vértice por visitar, sacamos el elemento 5 de la pila como se muestra a continuación:

No podemos avanzar más 5, por lo que debemos realizar un retroceso. Al retroceder, el elemento superior saldría de la pila. El elemento superior es el 5 que saldrá de la pila y volvemos al nodo 2 como se muestra a continuación:

unix crear directorio

Ahora comprobaremos los vértices adyacentes no visitados del nodo 2. Como no queda ningún vértice adyacente por visitar, realizamos un retroceso. Al retroceder, el elemento superior, es decir, 2, saldrá de la pila y regresaremos al nodo 3 como se muestra a continuación:

Ahora comprobaremos los vértices adyacentes no visitados del nodo 3. Como no queda ningún vértice adyacente por visitar, realizamos un retroceso. Al retroceder, el elemento superior, es decir, 3, saldrá de la pila y regresaremos al nodo 1 como se muestra a continuación:

Después de extraer el elemento 3, verificaremos los vértices adyacentes no visitados del nodo 1. Dado que no queda ningún vértice por visitar; por lo tanto, se realizará el retroceso. Al retroceder, el elemento superior, es decir, 1, saldrá de la pila y regresaremos al nodo 0 como se muestra a continuación:

Comprobaremos los vértices adyacentes del nodo 0, que aún no están visitados. Como no queda ningún vértice adyacente por visitar, realizamos un retroceso. En esto, solo un elemento, es decir, el 0 que queda en la pila, saldrá de la pila como se muestra a continuación:

Como podemos observar en la figura anterior, la pila está vacía. Entonces, tenemos que detener el recorrido DFS aquí, y los elementos que se imprimen son el resultado del recorrido DFS.

Diferencias entre BFS y DFS

Las siguientes son las diferencias entre BFS y DFS: