example - depth first search graph
Estructura de datos gráficos: DFS vs BFS? (5)
Ambos recorridos de gráfico prometen una cosa: un recorrido completo del gráfico, visitando cada vértice del gráfico. Si no tiene restricciones de memoria, DFS es una buena opción, ya que BFS ocupa mucho espacio. Entonces, elegir entre estos dos depende de su requerimiento.
¿Quieres encontrar los componentes (fuerte /) conectados del gráfico? o resolver el laberinto o sudoku? Use DFS. Si observa detenidamente, el Pedido anticipado, el Pedido posterior y el Pedido son todas variantes del DFS. Entonces, sí, esas son algunas aplicaciones interesantes.
BFS si desea probar si un gráfico es bipartito, encuentre la ruta más corta entre dos nodos o aplicaciones que requieren tales tareas.
si se le presenta un problema de gráfico, ¿cómo sabemos si necesitamos usar el algoritmo bfs o dfs? o cuando usamos el algoritmo dfs o el algoritmo bfs. ¿Cuáles son las diferencias y ventajas de una sobre otra?
BFS es extremadamente bueno para las rutas más cortas, mientras que DFS no lo es.
En la cola de bfs se usa mientras que en la pila dfs se usa para almacenar vértices de acuerdo con el recorrido del gráfico.
2- en el proceso de bfs se realiza de nivel a nivel (de acuerdo con un gráfico dirigido o no dirigido) mientras que en dfs el proceso se realiza a profundidad (el proceso de visitar primero el nodo raíz y otro de hacerlo lejos y luego aplicar retroceso desde el último nodo a nodo raíz).
La amplitud busca primero a los hermanos. 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 en todos los campos probablemente se prestarían a bfs, donde jerárquico (árboles, carpetas, rangos, etc.) sería más apropiado como dfs.
BFS va a usar más memoria dependiendo del factor de bifurcación ... sin embargo, BFS es un algoritmo completo ... lo que significa que si lo está utilizando para buscar algo en la profundidad más baja 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 cantidad de memoria).
Por otro lado, DFS es mucho mejor con el espacio, pero puede encontrar una solución que no sea óptima. Es decir, si solo está buscando una ruta de un vértice a otro, puede encontrar la solución menos óptima (y detenerse ahí) 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 la ruta más larga posible.
Tienen la misma complejidad de tiempo.
En términos de implementación, BFS generalmente se implementa con Queue , mientras que DFS usa Stack .