La principal diferencia entre BFS y DFS es que BFS procede de nivel a nivel, mientras que DFS sigue primero una ruta desde el nodo inicial hasta el nodo final (vértice), luego otra ruta de principio a fin, y así sucesivamente hasta que se visitan todos los nodos. Además, BFS utiliza la cola para almacenar los nodos, mientras que DFS utiliza la pila para recorrer los nodos.
BFS y DFS son los métodos de recorrido utilizados en la búsqueda de un gráfico. El recorrido del gráfico es el proceso de visitar todos los nodos del gráfico. Un grafo es un grupo de vértices ‘ V ‘y Aristas’ E ‘ que se conectan a los vértices.
Contenido: BFS Vs DFS
- Comparison Chart
- Definition
- Key Differences
- Conclusion
Comparison Chart
| Basis for comparison | BFS | DFS |
|---|---|---|
| Basic | Vertex-based algorithm | Edge-based algorithm |
| Data structure used to store the nodes | Queue | Stack |
| Memory consumption | Inefficient | Efficient |
| Structure del árbol construido | Ancho y corto | Estrecho y largo |
| Moda transversal | Los vértices no visitados más antiguos se exploran al principio. | Los vértices a lo largo del borde se exploran al principio. |
| Optimalidad | Óptimo para encontrar la distancia más corta, no en el costo. | No es óptimo |
| La aplicación | Examina el gráfico bipartito, el componente conectado y la ruta más corta presentes en un gráfico. | Examina el grafo conectado de dos aristas, el grafo fuertemente conectado, el grafo acíclico y el orden topológico. |
Definición de BFS
Amplitud Primera Búsqueda (BFS) es la de atravesar el método utilizado en los gráficos. Utiliza una cola para almacenar los vértices visitados. En este método, el énfasis está en los vértices del gráfico, se selecciona un vértice al principio, luego se visita y se marca. Los vértices adyacentes al vértice visitado se visitan y almacenan en la cola de forma secuencial.
De manera similar, los vértices almacenados se tratan uno por uno, y se visitan sus vértices adyacentes. Un nodo se explora completamente antes de visitar cualquier otro nodo en el gráfico, en otras palabras, atraviesa primero los nodos inexplorados más superficiales.
Ejemplo
Tenemos un grafo cuyos vértices son a, B, C, D, E, F, G. Considerando como punto de partida. Los pasos involucrados en el proceso son:
- El vértice A se expande y se almacena en la cola.
- Los vértices B, D y G sucesores de A, se expanden y se almacenan en la cola mientras se elimina el vértice A.
- Ahora B en el extremo frontal de la cola se elimina junto con el almacenamiento de sus vértices sucesores E y F.
- El vértice D se encuentra en el extremo frontal de la cola se elimina, y su nodo conectado F ya está visitado.
- El vértice G se elimina de la cola, y tiene el sucesor E que ya está visitado.
- Ahora E y F se eliminan de la cola, y su vértice sucesor C se atraviesa y se almacena en la cola.
- Al final C también se elimina y la cola está vacía, lo que significa que hemos terminado.
- La Salida generada es – a, B, D, G, E, F, C.
Aplicaciones
BFS puede ser útil para encontrar si el gráfico tiene componentes conectados o no. Y también se puede usar para detectar un gráfico bipartito.
Un grafo es bipartito cuando los vértices del grafo se dividen en dos conjuntos disjuntos; no hay dos vértices adyacentes que residan en el mismo conjunto. Otro método para verificar un gráfico bipartito es verificar la ocurrencia de un ciclo impar en el gráfico. Un gráfico bipartito no debe contener un ciclo impar.
BFS también es mejor para encontrar el camino más corto en el gráfico que podría verse como una red.
Definición de DFS
El método de recorrido de búsqueda en profundidad (DFS) utiliza la pila para almacenar los vértices visitados. DFS es el método basado en bordes y funciona de manera recursiva donde los vértices se exploran a lo largo de un camino (borde). La exploración de un nodo se suspende tan pronto como se encuentra otro nodo inexplorado y se atraviesan los nodos inexplorados más profundos. DFS recorre / visita cada vértice exactamente una vez y cada borde se inspecciona exactamente dos veces.
Ejemplo
Similar a BFS permite tomar el mismo gráfico para realizar operaciones DFS, y los pasos involucrados son:
- Considerando A como el vértice inicial que se explora y almacena en la pila.
- El vértice sucesor de B de A se almacena en la pila.
- El vértice B tiene dos sucesores E y F, entre ellos alfabéticamente E se explora primero y se almacena en la pila.
- El sucesor del vértice E, es decir, G, se almacena en la pila.
- El vértice G tiene dos vértices conectados, y ambos ya están visitados, por lo que G sale de la pila.
- Del mismo modo, E s también se elimina.
- Ahora, el vértice B está en la parte superior de la pila, su otro nodo(vértice) F se explora y almacena en la pila.
- El Vértice F tiene dos sucesores C y D, entre ellos C se atraviesa primero y se almacena en la pila.
- El Vértice C solo tiene un predecesor que ya está visitado, por lo que se elimina de la pila.
- Ahora el vértice D conectado a F se visita y se almacena en la pila.
- Como el vértice D no tiene nodos no visitados, por lo tanto, D se elimina.
- Del mismo modo, F, B y A también se activan.
- La salida generada es – a, B, E, G, F, C, D.
Aplicación
Las aplicaciones de DFS incluyen la inspección de un gráfico conectado de dos bordes, un gráfico fuertemente conectado, un gráfico acíclico y un orden topológico.
Un gráfico se denomina dos aristas conectadas si y solo si permanece conectado incluso si se elimina una de sus aristas. Esta aplicación es muy útil, en redes de computadoras donde el fallo de un enlace en la red no afectará a la red restante, y aún estaría conectada.
El grafo fuertemente conectado es un grafo en el que debe existir una ruta entre pares ordenados de vértices. DFS se utiliza en el gráfico dirigido para buscar la ruta entre cada par de vértices ordenados. DFS puede resolver fácilmente los problemas de conectividad.
Diferencias clave entre BFS y DFS
- BFS es un algoritmo basado en vértices, mientras que DFS es un algoritmo basado en bordes.
- La estructura de datos de cola se utiliza en BFS. Por otro lado, DFS utiliza pila o recursión.
- El espacio de memoria se utiliza de manera eficiente en DFS, mientras que la utilización del espacio en BFS no es efectiva.
- BFS es un algoritmo óptimo, mientras que DFS no es óptimo.
- DFS construye árboles estrechos y largos. En cambio, BFS construye un árbol ancho y corto.
Conclusión
BFS y DFS, ambas técnicas de búsqueda de gráficos tienen un tiempo de ejecución similar pero un consumo de espacio diferente, DFS toma espacio lineal porque tenemos que recordar una ruta única con nodos inexplorados, mientras que BFS mantiene cada nodo en memoria.
DFS produce soluciones más profundas y no es óptimo, pero funciona bien cuando la solución es densa, mientras que BFS es óptimo, que busca el objetivo óptimo al principio.