Por supuesto no. Estos algoritmos son exactamente equivalentes.
Como saben, la única diferencia efectiva entre DFS y BFS es el tipo de estructura de datos que utilizamos para realizar un seguimiento de los nodos que se encuentran en nuestra “ruta de descubrimiento”.
En BFS, utilizamos un principio de Primero en entrar, primero en salir, porque vamos “primero en amplitud”. Es decir, cuando estoy procesando un nodo, quiero procesar a todos sus vecinos, antes de pasar a otros nodos más profundos. Por lo tanto, utilizamos una cola, y eso nos permite pelar una capa de profundidad a la vez, explorando todo el ancho de una capa más superficial de nodos antes de pasar a los más profundos.
- Cómo ordenar la lista en la columna como números y cadena, pero la cadena no se debe ordenar en Excel
- ¿Qué técnicas se utilizan para calcular las probabilidades de caída de elementos en los juegos?
- ¿Cómo verificamos la corrección de un algoritmo?
- ¿Es posible implementar algoritmos de aprendizaje automático en lenguaje ensamblador?
- ¿Cuáles son algunos proyectos que podrían realizarse utilizando estructuras de datos?
Por otro lado, DFS, al ser “primero en profundidad”, requiere que hagamos todo lo contrario: profundizar antes de ir a lo ancho. Entonces, dado que lo más profundo debería venir antes , empleamos un enfoque de último en entrar , primero en salir, mediante el uso de una pila.
Sin esa diferencia, el algoritmo se reduce a “elegir un nodo de un almacén de nodos, procesarlo de alguna manera y luego agregar sus vecinos al almacén de nodos ”
Entonces, ¿se trata de si es “más rápido o más eficiente” usar una cola o una pila? Estoy seguro de que puede ver cómo se pueden implementar ambos para tener O (1) operaciones push y pop con las mismas estructuras de datos subyacentes, por lo que su rendimiento es bastante similar.
