Nadie ha mencionado un factor clave en los casos en que la búsqueda de amplitud es útil: visitar un nodo de una manera puede eliminar el requisito de visitar el nodo de otra manera.En algunos casos, uno terminará haciendo el mismo trabajo independientemente del orden en que se visiten los nodos, pero BFS tendrá muchas menos acciones pendientes a la vez que DFS. En otros casos, visitar nodos en una secuencia puede requerir más trabajo que otros; varios algoritmos de ruta más corta se dan como un ejemplo de eso. Si visitar un nodo requiere visitar a sus vecinos a menos que se sepa que el nodo es accesible por una ruta más corta que la actual, visitar los nodos en orden de amplitud típicamente dará como resultado que los nodos tengan asignada la ruta más corta, o algo cercano a ella. en su primera visita Por el contrario, una búsqueda en profundidad haría que muchos nodos fueran visitados por caminos muy largos la primera vez, luego por caminos ligeramente más cortos, luego por caminos ligeramente más cortos, etc., que requerían una cantidad total de trabajo realmente monstruosa.
BTW, una bonita ilustración gráfica de la diferencia entre los algoritmos primero en profundidad y ancho es un relleno de inundación de área, donde un nodo blanco está lleno de inundaciones pintándolo de negro y llenando de inundación a sus vecinos. Si se intenta rellenar un área cuadrada NxN comenzando en un maíz, una operación de profundidad llenaría el cuadrado en una secuencia en espiral o en zig-zag, con operaciones NxN-1 restantes en la pila. Un relleno de ancho primero se "vierta" desde el punto de inicio y tiene como máximo O (N) operaciones pendientes, independientemente de la forma que se llene. Por cierto, el relleno de inundación en IBM BASICA funcionó de esa manera (no estoy seguro acerca de QBASIC).
Parece que debería ser un caso bastante extremo para que un BFS ocupe menos espacio que un DFS, considerando que la complejidad del espacio de un BFS es b^d. –
Después de refrescarme en lo que realmente quiero decir con b y d en mi comentario anterior, recordé que cada nodo que tenga un nodo hijo sería 1^d. Por lo tanto, supongo que tener solo un nodo hijo * sería * un caso extremo. :-) –