stack - profundidad - ¿Cómo puedo recordar qué estructuras de datos utilizan DFS y BFS?
dfs grafos (13)
Siempre me confundo si utilizo una pila o una cola para DFS o BFS. ¿Puede alguien proporcionar alguna intuición sobre cómo recordar qué algoritmo usa qué estructura de datos?
Bfs; Amplitud => cola
Dfs; Depth => stack
Consulte su estructura.
Stack (Last In First Out, LIFO). Para DFS, lo recuperamos de la raíz al nodo más lejano tanto como sea posible, esta es la misma idea que LIFO.
Cola (Primero en entrar, primero en salir, FIFO). Para BFS, lo recuperamos un nivel por un nivel, después de visitar el nivel superior del nodo, visitamos el nivel inferior del nodo, esta es la misma idea que FIFO.
BFS explora / procesa los vértices más cercanos primero y luego se aleja de la fuente. Teniendo en cuenta esto, desea utilizar una estructura de datos que, cuando se le consulta, le proporciona el elemento más antiguo, en función del orden en que se insertaron. Una cola es lo que necesita en este caso, ya que es el primero en entrar, el primero en salir (FIFO). Mientras que un DFS explora lo más lejos posible a lo largo de cada rama primero y luego las pistas de soporte. Para esto, una pila funciona mejor ya que es LIFO (último en entrar, primero en salir)
BFS usa siempre la cola, Dfs usa la estructura de datos de la Pila. Como se explica en la explicación anterior sobre DFS, se está utilizando la función de retroceso. Recuerde que el retroceso puede proceder solo por Pila.
Dibuje un pequeño gráfico en una hoja de papel y piense en el orden en que se procesan los nodos en cada implementación. ¿En qué se diferencia el orden en el que encuentra los nodos y el orden en que procesa los nodos entre las búsquedas?
Uno de ellos usa una pila (primero en profundidad) y el otro usa una cola (primero en ancho) (al menos para implementaciones no recursivas).
Lo recuerdo manteniendo a Barbecue en mi mente. La barbacoa comienza con una ''B'' y termina con un sonido como ''q'', por lo tanto BFS -> Queue y las restantes DFS -> stack.
Me gustaría compartir esta respuesta: https://.com/a/20429574/3221630
Tomando BFS y reemplazando la cola con una pila, reproduce el mismo orden de visitas de DFS, usa más espacio que el algoritmo DFS real.
No recuerdo nada.
Suponiendo que la estructura de datos utilizada para la búsqueda es X :
Amplitud Primero = Los nodos ingresados X antes, deben generarse primero en el árbol: X es una cola.
Profundidad Primero = Los nodos ingresados X más tarde, deben generarse primero en el árbol: X es una pila.
En resumen: Stack es el último en entrar, el primero en salir, que es DFS. La cola es el primero en entrar, el primero en salir, que es BFS.
Puedes recordar haciendo un acrónimo.
BQDS
Bella reina ha hecho pecados.
En hindi, हुरानी क्यु द र्द स हा
Tómalo en orden alfabético ...
.... B (BFS) ..... C ...... D (DFS) ....
.... Q (cola) ... R ...... S (pila) ...
Una forma más fácil de recordar, especialmente para los estudiantes jóvenes, es usar un acrónimo similar:
BFS => Boy FriendS en cola (aparentemente para damas populares).
DFS es de otra manera (pila).
La cola se puede pensar generalmente como horizontal en su estructura, es decir, se puede atribuir ancho / ancho - BFS , mientras que
La pila se visualiza como una estructura vertical y, por lo tanto, tiene profundidad : DFS .
La búsqueda en profundidad utiliza una Stack para recordar dónde debe ir cuando llega a un callejón sin salida.
DFSS