Solución:
BFS utilizará más memoria dependiendo del factor de ramificación … sin embargo, BFS es un algoritmo completo … lo que significa que si lo está utilizando para buscar algo en la menor profundidad posible, BFS le dará la solución óptima. La complejidad del espacio BFS es O(b^d)… el factor de ramificación elevado a la profundidad (puede ser MUCHA memoria).
DFS, por otro lado, es mucho mejor con respecto al espacio, sin embargo, puede encontrar una solución subóptima. Es decir, si solo está buscando una ruta de un vértice a otro, puede encontrar la solución subóptima (y detenerse allí) antes de encontrar la ruta más corta real. La complejidad del espacio DFS es O(|V|)… lo que significa que la mayor cantidad de memoria que puede ocupar es el camino más largo posible.
Tienen la misma complejidad de tiempo.
En términos de implementación, BFS generalmente se implementa con Queue, mientras que DFS usa un Stack.
amplitud primero busca hermanos primero. la profundidad primero, obviamente, busca a los niños primero. Entonces, supongo que dependerá del tipo de búsqueda que estés buscando hacer. Las búsquedas de tipo de relación entre campos probablemente se presten a bfs, donde las jerárquicas (árboles, carpetas, rangos, etc.) serían más adecuadas como dfs.
Ambos recorridos del gráfico prometen una cosa: un recorrido completo del gráfico, visitando todos los vértices del gráfico. Si tiene limitaciones de memoria, DFS es una buena opción, ya que BFS ocupa mucho espacio. Por lo tanto, elegir entre estos dos depende de sus requisitos.
¿Quiere encontrar los componentes (fuertemente /) conectados del gráfico? ¿O resolver el laberinto? ¿O sudoku? Utilice DFS. Si observa detenidamente, el pedido anticipado, el pedido posterior y el pedido en pedido son todas variantes del DFS. Entonces, sí, esas son algunas aplicaciones interesantes.
BFS si desea probar si un gráfico es bipartito, busque la ruta más corta entre dos nodos o aplicaciones que requieran tales tareas.