Diferencia entre BFS VS DFS
Breadth-First Search (BFS) y Depth First Search (DFS) son dos algoritmos importantes utilizados para la búsqueda. Breadth-First Search comienza su búsqueda desde el primer nodo y luego se mueve a través de los niveles que están más cerca del nodo raíz, mientras que el algoritmo Depth First Search comienza con el primer nodo y luego completa su ruta al nodo final de la ruta respectiva. Ambos algoritmos atraviesan cada nodo durante la búsqueda. Se escriben diferentes códigos para los dos algoritmos para ejecutar el proceso de desplazamiento. También se consideran algoritmos de búsqueda importantes en Inteligencia Artificial.
En este tema, vamos a aprender sobre BFS VS DFS.
¿Cómo funcionan BFS y DFS?
El mecanismo de trabajo de ambos algoritmos se explica a continuación con ejemplos. Por favor, consúltelos para comprender mejor el enfoque utilizado.
Breadth-First Ejemplo de búsqueda
- Paso 1: N1 es el nodo raíz, por lo que comenzará desde aquí. N1 está conectado con tres nodos N2, N3 y N4. Los tres nodos aún no se han visitado. Entonces, comenzamos desde N2 y lo almacenamos en la cola. Entonces, la cola llamada Q contiene solo N2.
Q: N2
- Paso 2: a continuación, el nodo que está conectado a N1 es N3. Como cruzamos o visitamos el nodo, lo almacenaremos en la cola. Entonces, la cola actualizada es
Q: N3, N2
- Paso 3: a continuación, el nodo que está conectado al nodo raíz es N4. Lo almacenaremos en la cola.
Q: N4, N3, N2
- Paso 4: todos los nodos que están conectados a N1 se almacenan en la cola. Ahora, eliminamos N2 de la cola según el principio Primero en entrar, primero en salir (FIFO) y encontramos los nodos que están conectados al N2, es decir, N5. N5 no se visita una vez, por lo que lo almacenaremos en la cola.
Q: N5, N4, N3
- Paso 5: se visitan todos los vértices, por lo que seguimos eliminando los nodos de la cola hasta que esté vacío.
Profundidad Primer ejemplo de búsqueda
- Paso 1: Comenzaremos con N1 como el nodo inicial y lo almacenaremos en una pila S. N1 está conectado con tres nodos vecinos N2, N3 y N4. Comenzando con N2 (puede comenzar alfabéticamente o numéricamente), lo pondremos en la pila.
S: N2 (arriba), N1
- Paso 2: Ahora, los nodos vecinos de N2 son N1 y N5. Como N1 ya está presente en la pila, eso significa que se visita, por lo que tomaremos N5 y lo colocaremos en la pila S.
S: N5 (arriba), N2, N1
- Paso 3: Ahora, los nodos vecinos de N5 son N3 y N4. Comenzamos será N3 y lo pondremos en la pila.
S: N3 (arriba), N5, N2, N1
Ahora N3 está conectado a N5 y N1 que ya están presentes en la pila, lo que significa que son visitados, por lo que eliminaremos N3 de la pila según el principio del principio Último en salir primero (LIFO).
S: N5 (arriba), N2, N1
- Paso 4: Ahora colocaremos el último nodo que no encontramos en todo el recorrido en N4 y lo colocaremos en la pila.
S: N4 (arriba), N5, N2, N1
- Paso 5: Ahora no nos quedamos fuera con ningún otro nodo, por lo que revisaremos en la pila si hay nodos conectados a los respectivos nodos presentes en él que no se visitan. Si se visitan todos los nodos conectados, eliminaremos los nodos presentes en la pila. Por ejemplo, N4 no tiene nodos de conexión que no verificamos, por lo que lo eliminaremos de la pila. Del mismo modo, podemos verificar otros nodos. El algoritmo se detiene una vez que la pila está vacía.
Comparación cabeza a cabeza entre BFS y DFS (infografía)
A continuación se presentan las 6 principales diferencias entre BFS VS DFS
Diferencias clave entre BFS y DFS
Discutamos algunas de las principales diferencias clave entre BFS y DFS
- Breadth-First Search (BFS) comienza desde el nodo raíz y visita todos los nodos respectivos conectados a él, mientras que DFS comienza desde el nodo raíz y completa la ruta completa adjunta al nodo.
- BFS sigue el enfoque de Queue mientras que DFS sigue el enfoque de Stack.
- El enfoque utilizado en BFS es óptimo, mientras que el proceso utilizado en DFS no es óptimo.
- Si nuestro objetivo es encontrar la ruta más corta, se prefiere BFS a DFS.
Tabla de comparación de BFS y DFS
Analicemos la comparación principal entre BFS y DFS
| BFS | DFS |
| La forma completa de BFS es Breadth-First Search. | La forma completa de DFS es Profundidad Primero Búsqueda |
| BFS está destinado a encontrar la distancia más corta y comienza desde el primer nodo o raíz y se mueve a través de todos sus nodos conectados a los nodos respectivos. Puede obtener una visión clara de su mecanismo de trabajo después de seguir el siguiente ejemplo. | DFS sigue un enfoque basado en la profundidad y completa la ruta completa a través de todos los nodos conectados al nodo respectivo. Puede obtener una visión clara de su mecanismo de trabajo después de seguir el siguiente ejemplo. |
| Se realiza utilizando el principio de cola, que es el enfoque Primero en entrar, primero en salir (FIFO). | Se realiza utilizando el principio de Pila, que es el enfoque Último en entrar, primero en salir (LIFO). |
| Los nodos que se atraviesan más de una vez se eliminan de la cola. | Los nodos que se visitan se insertan en la pila y luego, si no hay más nodos para visitar, se eliminan. |
| Es comparativamente más lento que Depth First Search. | Es más rápido que el algoritmo Breadth-First Search. |
| La asignación de memoria es más que el algoritmo de búsqueda en profundidad. | La asignación de memoria es comparativamente menor que el algoritmo de búsqueda de Breadth-First |
Conclusión
Hay muchas aplicaciones en las que los algoritmos anteriores se utilizan como aprendizaje automático o para encontrar soluciones relacionadas con la inteligencia artificial, etc. Se utilizan principalmente en gráficos para determinar si es bipartito o no, para detectar ciclos o componentes que están conectados. También se consideran algoritmos importantes para encontrar el camino o para encontrar la distancia más corta. Dependiendo de los requisitos del negocio, podemos usar dos algoritmos. Sin embargo, Breadth-First Search se considera una forma óptima en lugar del algoritmo Depth First Search.
Artículos recomendados
Esta es una guía de BFS VS DFS. Aquí discutimos las diferencias clave BFS VS DFS con infografías y tabla de comparación. También puede echar un vistazo a los siguientes artículos para obtener más información:
- Algoritmo BFS
- TeraData vs Oracle
- Big Data vs Data Warehouse
- Big Data vs Apache Hadoop: comparación de los 4 principales que debe aprender