BFS y DFS son los métodos de desplazamiento 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 gráfico es un grupo de vértices 'V' y bordes E 'que se conectan a los vértices.
Gráfica comparativa
| Bases para la comparación | BFS | DFS |
|---|---|---|
| BASIC | Algoritmo basado en vértice | Algoritmo basado en bordes |
| Estructura de datos utilizada para almacenar los nodos. | Cola | Apilar |
| Consumo de memoria | Ineficiente | Eficiente |
| Estructura del árbol construido. | Ancho y corto | Estrecho y largo. |
| Atravesando la moda | 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 costo. | No optimo |
| Solicitud | Examina el gráfico bipartito, el componente conectado y la ruta más corta presente en un gráfico. | Examina el gráfico conectado de dos bordes, el gráfico fuertemente conectado, el gráfico acíclico y el orden topológico. |
Definición de BFS
La búsqueda en primer lugar (BFS) es el método de desplazamiento 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, al principio se selecciona un vértice y 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 menos explorados.
Ejemplo
Tenemos una gráfica cuyos vértices son A, B, C, D, E, F, G. Considerando A como punto de partida. Los pasos involucrados en el proceso son:
- El vértice A se expande y se almacena en la cola.
- Los sucesores de los vértices B, D y G de A se expanden y almacenan en la cola mientras se elimina el vértice A.
- Ahora se elimina B en el extremo frontal de la cola junto con el almacenamiento de sus vértices sucesores E y F.
- El vértice D está en el extremo frontal de la cola, se elimina y su nodo F ya está visitado.
- El vértice G se elimina de la cola y tiene el sucesor E que ya se ha visitado.
- Ahora E y F se eliminan de la cola, y su vértice sucesor C se recorre y se almacena en la cola.
- Por último, 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.
BFS puede ser útil para determinar si el gráfico tiene componentes conectados o no. Y también se puede utilizar para detectar un gráfico bipartito .
Una gráfica es bipartita cuando los vértices de la gráfica se dividen en dos conjuntos separados; no hay dos vértices adyacentes que residirían 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 la ruta más corta en el gráfico que podría verse como una red.
Definición de DFS
El método de desplazamiento 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 una trayectoria (borde). La exploración de un nodo se suspende tan pronto como se encuentra otro nodo inexplorado y los nodos no explorados más profundos se recorren en primer lugar. El DFS atraviesa / 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 de inicio que se explora y almacena en la pila.
- El vértice sucesor B de A se almacena en la pila.
- Los vértices B tienen 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.
- Los vértices G tienen dos vértices conectados, y ambos ya están visitados, por lo que G se extrae de la pila.
- Del mismo modo, E s también eliminado.
- 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 recorre primero y se almacena en la pila.
- Vertex C solo tiene un predecesor que ya se ha visitado, por lo que se elimina de la pila.
- Ahora el vértice D conectado a F es visitado y almacenado en la pila.
- Como el vértice D no tiene nodos no visitados, se elimina D.
- Del mismo modo, F, B y A también se saltan.
- La salida generada es - A, B, E, G, F, C, D.
Las aplicaciones de DFS incluyen la inspección de dos gráficos conectados por bordes, gráficos fuertemente conectados, gráficos acíclicos y orden topológico .
Un gráfico se llama dos bordes conectados solo si permanece conectado aunque se elimine uno de sus bordes. Esta aplicación es muy útil en redes de computadoras donde la falla de un enlace en la red no afectará a la red restante y aún estaría conectada.
El gráfico fuertemente conectado es un gráfico en el que debe existir una ruta entre un par de vértices ordenados. DFS se usa en el gráfico dirigido para buscar la ruta entre cada par de vértices ordenados. DFS puede resolver fácilmente 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 la cola se utiliza en BFS. Por otro lado, DFS usa stack o recursión.
- El espacio de memoria se utiliza de manera eficiente en DFS, mientras que la utilización de espacio en BFS no es efectiva.
- BFS es un algoritmo óptimo mientras que DFS no es óptimo.
- DFS construye árboles estrechos y largos. En contra, BFS construye un árbol ancho y corto.
Conclusión
BFS y DFS, ambas técnicas de búsqueda gráfica tienen un tiempo de ejecución similar pero un consumo de espacio diferente, DFS toma espacio lineal porque tenemos que recordar una sola ruta con nodos no explorados, mientras que BFS mantiene todos los nodos en la memoria.
El DFS produce soluciones más profundas y no es óptimo, pero funciona bien cuando la solución es densa, mientras que BFS es óptimo, lo que busca el objetivo óptimo al principio.
