BFS vs DFS: conozca la diferencia

¿Qué es BFS? ?

BFS es un algoritmo que se utiliza para graficar datos o buscar árboles o estructuras de desplazamiento. El algoritmo visita y marca de manera eficiente todos los nodos clave en un gráfico de manera precisa a lo ancho.

Este algoritmo selecciona un solo nodo (punto inicial o fuente) 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 mueve hacia los nodos no visitados más cercanos y los analiza.

Una vez visitado, se marcan todos los nodos. Estas iteraciones continúan hasta que todos los nodos del gráfico se hayan visitado y marcado con éxito. La forma completa de BFS es la búsqueda en amplitud primero.

En este BSF Vs. Tutorial de árbol binario DFS, aprenderá:

• ¿Qué es BFS?
• ¿Qué es DFS?
• Ejemplo de BFS
• Ejemplo de DFS
• Diferencia entre BFS y DFS Binary Tree
• Aplicaciones de BFS
• Aplicaciones de DFS

¿Qué es DFS?

DFS es un algoritmo para encontrar o recorrer gráficos o árboles en dirección de profundidad. 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 posterior y comenzar una búsqueda, siempre que aparezca un callejón sin salida en cualquier iteración. La forma completa de DFS es la búsqueda en profundidad.

Ejemplo de BFS

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

Ejemplo de BFS

Paso 1)

Tiene una gráfica 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 es visitado, marcado y se inserta en la estructura de datos de la cola.

Paso 4)

Permaneciendo 0 adyacentes y no visitados los nodos se visitan, se marcan y se insertan en la cola.

Paso 5)

Las iteraciones de desplazamiento se repiten hasta 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 de visitados y colocando simultáneamente todos sus vértices adyacentes en los datos estructura llamada pila.

Paso 2)

Visitarás el elemento , que está en la parte superior de la pila, por ejemplo, 1 y vaya a sus nodos adyacentes. Es porque ya se ha visitado 0. Por lo 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 en 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 mediante el algoritmo DFS.

Diferencia entre BFS y DFS Binary Tree

BFS	DFS
BFS encuentra la ruta más corta al destino.	DFS va al final de un subárbol, luego retrocede .
La forma completa de BFS es búsqueda primero en amplitud.	La forma completa de DFS es búsqueda primero en profundidad.
Utiliza una cola para realizar un seguimiento de la siguiente ubicación a visitar.	Utiliza una pila para realizar un seguimiento de la siguiente ubicación a visitar.
BFS atraviesa según el nivel del árbol.	DFS atraviesa según la profundidad del árbol.
Se implementa mediante FI Lista de FO.	Se implementa usando 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 ruta más superficial.	Este algoritmo no garantiza la solución de ruta más superficial.
No hay necesidad de retroceder en BFS.	Hay una necesidad de retroceder en DFS.
Nunca puede quedar atrapado en bucles finitos.	Puede 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 el nodo hoja retroceda ocurrir.

Aplicaciones de BFS

Aquí están las aplicaciones de BFS:

Sin ponderar Gráficos:

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:

BFS se puede implementar para ubicar todos los nodos más cercanos o vecinos en una red peer to peer. Esto encontrará los datos requeridos más rápido.

Rastreadores web:

Los motores de búsqueda o los rastreadores web pueden crear fácilmente varios 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.

Red de difusión:

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

Estas son aplicaciones importantes de DFS:

Gráfico ponderado:

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

Detección de un ciclo en un gráfico:

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

Búsqueda de ruta:

Podemos especializarnos en el algoritmo DFS para buscar una ruta entre dos vértices.

Clasificación topológica:

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

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

Se usa en el gráfico DFS cuando hay una ruta desde todos y cada uno de los vértices del gráfico a otros 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 al incluir nodos en la ruta existente en el conjunto visitado.