BFS vs DFS: diferencia entre ellos

¿Qué es BFS?

BFS es un algoritmo que se utiliza para graficar datos o buscar árboles o recorrer estructuras. El algoritmo visita y marca de manera eficiente todos los nodos clave de un gráfico de manera precisa y en toda su amplitud.

Este algoritmo selecciona un único nodo (punto inicial o de origen) en un gráfico y luego visita todos los nodos adyacentes al nodo seleccionado. Una vez que el algoritmo visita y marca el nodo de inicio, se desplaza hacia los nodos no visitados más cercanos y los analiza.

Una vez visitados, todos los nodos están marcados. Estas iteraciones continúan hasta que todos los nodos del gráfico hayan sido visitados y marcados con éxito. La forma completa de BFS es la búsqueda en amplitud.

¿Qué es DFS?

DFS es un algoritmo para buscar o atravesar gráficos o árboles en dirección profunda. La ejecución del algoritmo comienza en el nodo raíz y explora cada rama antes de retroceder. Utiliza una estructura de datos de pila para recordar, obtener el vértice siguiente e iniciar una búsqueda, cada vez que aparece un callejón sin salida en cualquier iteración. La forma completa de DFS es búsqueda en profundidad.

Diferencia entre el árbol binario BFS y DFS

Estas son las diferencias importantes entre BFS y DFS.

BFS	DFS
BFS encuentra el camino más corto hacia el destino.	DFS va al final de un subárbol y luego retrocede.
La forma completa de BFS es Breadth-First Search.	La forma completa de DFS es Búsqueda en profundidad.
Utiliza una cola para realizar un seguimiento del próximo lugar a visitar.	Utiliza una pila para realizar un seguimiento del próximo lugar a visitar.
BFS atraviesa según el nivel del árbol.	DFS atraviesa según la profundidad del árbol.
Se implementa utilizando la lista FIFO.	Se implementa utilizando la lista LIFO.
Requiere más memoria en comparación con DFS.	Requiere menos memoria en comparación con BFS.
Este algoritmo proporciona la solución de camino menos profundo.	Este algoritmo no garantiza la solución del camino menos profundo.
No es necesario retroceder en BFS.	Es necesario retroceder en DFS.
Nunca podrás quedar atrapado en bucles finitos.	Puedes quedar atrapado en bucles infinitos.
Si no encuentra ningún objetivo, es posible que deba expandir muchos nodos antes de encontrar la solución.	Si no encuentra ningún objetivo, es posible que se produzca un retroceso del nodo hoja.

Ejemplo de BFS

En el siguiente ejemplo de BFS, hemos utilizado un gráfico que tiene 6 vértices.

Ejemplo de BFS

Paso 1)

Tienes un gráfico de siete números que van del 0 al 6.

Paso 2)

Se ha marcado 0 o cero como nodo raíz.

Paso 3)

0 se visita, se marca y se inserta en la estructura de datos de la cola.

Paso 4)

Los 0 nodos adyacentes y no visitados restantes se visitan, marcan e insertan en la cola.

Paso 5)

Las iteraciones de recorrido se repiten hasta que se visitan todos los nodos.

Ejemplo de DFS

En el siguiente ejemplo de DFS, hemos utilizado un gráfico no dirigido que tiene 5 vértices.

Paso 1)

Hemos comenzado desde el vértice 0. El algoritmo comienza poniéndolo en la lista visitada y poniendo simultáneamente todos sus vértices adyacentes en la estructura de datos llamado pila.

Paso 2)

Visitará el elemento que está en la parte superior de la pila, por ejemplo 1, e irá a sus nodos adyacentes. Es porque 0 ya ha sido visitado. Por tanto, visitamos el vértice 2.

Paso 3)

El vértice 2 tiene un vértice cercano no visitado en 4. Por lo tanto, lo agregamos a la pila y lo visitamos.

Paso 4)

Finalmente visitaremos el último vértice 3, no tiene ningún nodo contiguo no visitado. Hemos completado el recorrido del gráfico utilizando el algoritmo DFS.

Aplicaciones de BFS

Aquí están las aplicaciones de BFS:

Gráficos no ponderados

El algoritmo BFS puede crear fácilmente la ruta más corta y un árbol de expansión mínimo para visitar todos los vértices del gráfico en el menor tiempo posible con alta precisión.

Redes P2P

Se puede implementar BFS para localizar todos los nodos más cercanos o vecinos en una red peer to peer. Esto permitirá encontrar los datos necesarios más rápidamente.

Rastreadores web

Los motores de búsqueda o los rastreadores web pueden crear fácilmente múltiples niveles de índices empleando BFS. La implementación de BFS comienza desde la fuente, que es la página web, y luego visita todos los enlaces de esa fuente.

Transmisión en red

Un paquete difundido es guiado por el algoritmo BFS para encontrar y llegar a todos los nodos para los que tiene la dirección.

Aplicaciones de DFS

Aquí hay aplicaciones importantes de DFS:

Gráfico ponderado

En un gráfico ponderado, el recorrido del gráfico DFS genera el árbol de ruta más corto y el árbol de expansión mínimo.

Detectar un ciclo en un gráfico

Un gráfico tiene un ciclo si encontramos un borde posterior durante DFS. Por lo tanto, debemos ejecutar DFS para el gráfico y verificar los bordes posteriores.

Encontrar camino

Podemos especializarnos en el algoritmo DFS para buscar un camino entre dos vértices.

Clasificación topológica

Se utiliza principalmente para programar tareas a partir de las dependencias dadas entre el grupo de tareas. En informática, se utiliza en la programación de instrucciones, serialización de datos, síntesis lógica y determinación del orden de las tareas de compilación.

Búsqueda de componentes fuertemente conectados de un gráfico

Se utiliza en el gráfico DFS cuando hay una ruta desde todos y cada uno de los vértices del gráfico hasta los demás vértices restantes.

Resolver acertijos con una sola solución

El algoritmo DFS se puede adaptar fácilmente para buscar todas las soluciones a un laberinto incluyendo nodos en la ruta existente en el conjunto visitado.