algorithm - first - Por qué DFS y no BFS para encontrar el ciclo en gráficos
depth first search geeksforgeeks (7)
Predominantemente DFS se usa para encontrar un ciclo en gráficos y no en BFS. ¿Alguna razón? Ambos pueden encontrar si ya se ha visitado un nodo al atravesar el árbol / gráfico.
- DFS es más fácil de implementar
- Una vez que DFS encuentra un ciclo, la pila contendrá los nodos que forman el ciclo. Lo mismo no es cierto para BFS, por lo que debe hacer un trabajo adicional si también desea imprimir el ciclo encontrado. Esto hace que DFS sea mucho más conveniente.
BFS no funcionará para un gráfico dirigido en los ciclos de búsqueda. Considere A-> B y A-> C-> B como caminos de A a B en un gráfico. BFS dirá que después de recorrer uno de los caminos que B visitó. Cuando continúe viajando en el siguiente camino, dirá que se ha encontrado nuevamente el nodo marcado B, por lo tanto, hay un ciclo allí. Claramente, no hay un ciclo aquí.
Depende de algo si estás hablando de implementaciones recursivas o iterativas.
Recursive-DFS visita cada nodo dos veces. Iterativo: BFS visita cada nodo una vez.
Si desea detectar un ciclo, debe investigar los nodos tanto antes como después de agregar sus adyacencias, tanto cuando "comienza" en un nodo como cuando "termina" con un nodo.
Esto requiere más trabajo en ITErative-BFS, por lo que la mayoría de las personas elige Recursive-DFS.
Tenga en cuenta que una implementación simple de Iterative-DFS con, por ejemplo, std :: stack tiene el mismo problema que Iterative-BFS. En ese caso, debe colocar elementos ficticios en la pila para realizar un seguimiento cuando "termine" de trabajar en un nodo.
Consulte esta respuesta para obtener más detalles sobre cómo Iterative-DFS requiere trabajo adicional para determinar cuándo "finaliza" con un nodo (respondido en el contexto de TopoSort):
Tipo topológico usando DFS sin recursión
Con suerte, eso explica por qué las personas prefieren Recursive-DFS para los problemas en los que debe determinar cuándo "termina" el procesamiento de un nodo.
La primera búsqueda de profundidad es más eficiente en cuanto a la memoria que la primera búsqueda de amplitud, ya que puede retroceder antes. También es más fácil de implementar si usa la pila de llamadas, pero esto se basa en la ruta más larga que no desborda la pila.
Además, si su gráfico está directed , no solo debe recordar si ha visitado un nodo o no, sino también cómo llegó allí. De lo contrario, podrías pensar que has encontrado un ciclo, pero en realidad todo lo que tienes son dos caminos separados A-> B, pero eso no significa que haya un camino B-> A. Por ejemplo,
Si haces BFS comenzando desde 0 , detectará como ciclo está presente pero en realidad no hay ciclo.
Con una primera búsqueda en profundidad, puede marcar los nodos como visitados mientras desciende y desmarcarlos mientras retrocede. Ver comentarios para una mejora del rendimiento en este algoritmo.
Para obtener el mejor algoritmo para detectar ciclos en un gráfico dirigido , puede ver el algoritmo de Tarjan .
Para demostrar que un gráfico es cíclico, solo necesita probar que tiene un ciclo (el borde apunta hacia sí mismo, ya sea directa o indirectamente).
En DFS tomamos un vértice a la vez y verificamos si tiene ciclo. Tan pronto como se encuentre un ciclo, podemos omitir la comprobación de otros vértices.
En BFS necesitamos hacer un seguimiento de muchos bordes de vértices simultáneamente y la mayoría de las veces al final descubrimos si tiene ciclo. A medida que crece el tamaño del gráfico, BFS requiere más espacio, computación y tiempo en comparación con DFS.
Si coloca un ciclo en un lugar al azar en un árbol, DFS tenderá a golpear el ciclo cuando está cubierto aproximadamente la mitad del árbol, y la mitad del tiempo ya habrá atravesado donde va el ciclo, y la mitad del tiempo no lo hará ( y lo encontrará en promedio en la mitad del resto del árbol), por lo que evaluará en promedio alrededor de 0.5 * 0.5 + 0.5 * 0.75 = 0.625 del árbol.
Si coloca un ciclo en un lugar al azar en un árbol, BFS tenderá a golpear el ciclo solo cuando se evalúe la capa del árbol a esa profundidad. Por lo tanto, por lo general, terminas teniendo que evaluar las hojas de un árbol binario de saldo, lo que generalmente resulta en la evaluación de más del árbol. En particular, 3/4 de las veces, al menos uno de los dos enlaces aparece en las hojas del árbol, y en esos casos debe evaluar un promedio de 3/4 del árbol (si hay un enlace) o 7 / 8 del árbol (si hay dos), por lo que ya está preparado para la búsqueda de 1/2 * 3/4 + 1/4 * 7/8 = (7 + 12) / 32 = 21/32 = 0.656 ... del árbol sin siquiera agregar el costo de buscar un árbol con un ciclo agregado fuera de los nodos de la hoja.
Además, DFS es más fácil de implementar que BFS. Por lo tanto, es el que debe usarse a menos que sepa algo acerca de sus ciclos (por ejemplo, es probable que los ciclos estén cerca de la raíz desde la cual realiza la búsqueda, en cuyo momento BFS le brinda una ventaja).
Un BFS podría ser razonable si el gráfico no está dirigido (¡seré invitado para mostrar un algoritmo eficiente usando BFS que informaría los ciclos en un gráfico dirigido!), Donde cada "borde cruzado" define un ciclo. Si el borde cruzado es {v1, v2} , y la raíz (en el árbol BFS) que contiene esos nodos es r , entonces el ciclo es r ~ v1 - v2 ~ r ( ~ es un camino, - un borde único), que se puede informar casi tan fácilmente como en DFS.
La única razón para usar un BFS sería si usted sabe que su gráfica (no dirigida) va a tener trayectorias largas y una cobertura de ruta pequeña (en otras palabras, profunda y estrecha). En ese caso, BFS requeriría proporcionalmente menos memoria para su cola que la pila DFS (ambas siguen siendo lineales, por supuesto).
En todos los demás casos, DFS es claramente el ganador. Funciona tanto en gráficos dirigidos como no dirigidos, y es trivial informar los ciclos, simplemente concatena cualquier borde posterior al camino desde el ancestro hasta el descendiente, y obtienes el ciclo. En general, es mucho mejor y más práctico que BFS para este problema.