¿Qué es BFS?
BFS es un algoritmo que se utiliza para graficar datos o buscar árboles o estructuras de recorrido. El algoritmo visita y marca de manera eficiente todos los nodos clave en un gráfico de manera precisa y amplia.
Este algoritmo selecciona un solo 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 mueve hacia los nodos no visitados más cercanos y los analiza.
Una vez visitados, 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 buscar 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, usamos un gráfico que tiene 6 vértices.
Ejemplo de BFS
Paso 1)
Tienes 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 se visita, marca e 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 que atraviesan 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 colocándolo en la lista de visitas y simultáneamente colocando todos sus vértices adyacentes en la estructura de datos llamada 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 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 nodos contiguos no visitados. Hemos completado el recorrido del gráfico utilizando 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 y luego retrocede. |
| La forma completa de BFS es Breadth-First Search. | La forma completa de DFS es Depth First Search. |
| Utiliza una cola para realizar un seguimiento de la próxima 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 usando la lista FIFO. | 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. | Es necesario retroceder en DFS. |
| Nunca puede quedar atrapado en bucles finitos. | Puede quedar atrapado en infinitos bucles. |
| 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, puede producirse el retroceso del nodo hoja. |
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:
BFS se puede implementar para ubicar todos los nodos más cercanos o vecinos en una red de igual a igual. 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.
Radiodifusión en red:
Un paquete transmitido 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 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, 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.
DIFERENCIAS CLAVE:
- BFS encuentra la ruta más corta al destino, mientras que DFS va al final de un subárbol y luego retrocede.
- La forma completa de BFS es Breadth-First Search, mientras que la forma completa de DFS es Depth First Search.
- BFS utiliza una cola para realizar un seguimiento de la próxima ubicación a visitar. mientras que DFS usa una pila para realizar un seguimiento de la próxima ubicación a visitar.
- BFS atraviesa según el nivel del árbol, mientras que DFS atraviesa según la profundidad del árbol.
- BFS se implementa usando la lista FIFO, por otro lado, DFS se implementa usando la lista LIFO.
- En BFS, nunca puede quedar atrapado en bucles finitos, mientras que en DFS puede quedar atrapado en bucles infinitos.