¿Por qué DFS y no BFS para encontrar ciclos en gráficos?

Predominantemente se utiliza DFS para encontrar un ciclo en gráficos y no BFS. ¿Alguna razón? Ambos pueden encontrar si un nodo ya ha sido visitado mientras atraviesan el árbol / gráfico.

La primera búsqueda en profundidad es más eficiente en la memoria que la búsqueda en 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 que la ruta más larga no desborde la pila.

Además, si su gráfico está dirigido , no solo debe recordar si ha visitado un nodo o no, sino también cómo llegó allí. De lo contrario, podría pensar que ha encontrado un ciclo, pero en realidad todo lo que tiene son dos caminos separados A-> B, pero eso no significa que haya un camino B-> A. Por ejemplo,

Si hace BFS a partir de 0, detectará que el ciclo está presente pero en realidad no hay ciclo.

Con una primera búsqueda en profundidad, puede marcar los nodos como visitados a medida que desciende y desmarcarlos cuando retrocede. Consulte los comentarios para ver una mejora del rendimiento de este algoritmo.

Para obtener el mejor algoritmo para detectar ciclos en un gráfico dirigido , puede consultar el algoritmo de Tarjan .

1. DFS es más fácil de implementar
2. Una vez que DFS encuentra un ciclo, la pila contendrá los nodos que forman el ciclo. No ocurre lo mismo con BFS, por lo que debe realizar un trabajo adicional si desea imprimir también el ciclo encontrado. Esto hace que DFS sea mucho más conveniente.

Un BFS podría ser razonable si el gráfico no está dirigido (¡sea mi invitado a mostrar un algoritmo eficiente usando BFS que reportaría los ciclos en un gráfico dirigido!), Donde cada "borde transversal" define un ciclo. Si el borde transversal 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 una ruta, -un solo borde), que se puede informar casi tan fácilmente como en DFS.

La única razón para usar un BFS sería si sabe que su gráfico (no dirigido) tendrá rutas 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 de DFS (ambos 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 concate cualquier borde posterior a la ruta del ancestro al descendiente, y obtendrás el ciclo. Considerándolo todo, mucho mejor y más práctico que BFS para este problema.

BFS no funcionará para un gráfico dirigido en la búsqueda de ciclos. 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 se visita B. Al continuar recorriendo el siguiente camino, dirá que el nodo marcado B se ha encontrado nuevamente, por lo tanto, hay un ciclo. Claramente, no hay ciclo aquí.

No sé por qué apareció una pregunta tan antigua en mi feed, pero todas las respuestas anteriores son malas, así que ...

DFS se usa para encontrar ciclos en gráficos dirigidos, porque funciona .

En un DFS, cada vértice se "visita", donde visitar un vértice significa:

1. Se inicia el vértice

2. Se visita el subgrafo accesible desde ese vértice. Esto incluye trazar todos los bordes no trazados que son accesibles desde ese vértice y visitar todos los vértices no visitados accesibles.

3. El vértice está terminado.

La característica crítica es que todos los bordes accesibles desde un vértice se trazan antes de que el vértice esté terminado. Esta es una característica de DFS, pero no BFS. De hecho, esta es la definición de DFS.

Debido a esta característica, sabemos que cuando se inicia el primer vértice de un ciclo:

1. No se ha trazado ninguno de los bordes del ciclo. Lo sabemos porque solo se puede llegar a ellos desde otro vértice del ciclo, y estamos hablando del primer vértice que se inicia.
2. Todas las aristas sin trazar a las que se pueda llegar desde ese vértice se trazarán antes de que finalice, y eso incluye todas las aristas del ciclo, porque todavía no se ha trazado ninguna. Por lo tanto, si hay un ciclo, encontraremos una arista de regreso al primer vértice después de que se inicia, pero antes de que termine; y
3. Dado que todos los bordes que se trazan son accesibles desde cada vértice iniciado pero no terminado, encontrar un borde en dicho vértice siempre indica un ciclo.

Entonces, si hay un ciclo, entonces tenemos la garantía de encontrar un borde a un vértice iniciado pero no terminado (2), y si encontramos dicho borde, entonces tenemos la garantía de que hay un ciclo (3).

Es por eso que DFS se usa para encontrar ciclos en gráficos dirigidos.

BFS no ofrece tales garantías, por lo que simplemente no funciona. (a pesar de los algoritmos de búsqueda de ciclos perfectamente buenos que incluyen BFS o similar como subprocedimiento)

Un gráfico no dirigido, por otro lado, tiene un ciclo siempre que hay dos caminos entre cualquier par de vértices, es decir, cuando no es un árbol. Esto es fácil de detectar durante BFS o DFS: los bordes trazados a nuevos vértices forman un árbol, y cualquier otro borde indica un ciclo.

Si coloca un ciclo en un lugar aleatorio de un árbol, DFS tenderá a golpear el ciclo cuando esté cubierto aproximadamente la mitad del árbol, y la mitad del tiempo ya habrá atravesado el lugar donde va el ciclo, y la mitad de las veces 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 aleatorio de un árbol, BFS tenderá a golpear el ciclo solo cuando se evalúa la capa del árbol a esa profundidad. Por lo tanto, generalmente termina teniendo que evaluar las hojas de un árbol binario de equilibrio, lo que generalmente da como resultado evaluar 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 hay que evaluar en promedio 3/4 del árbol (si hay un enlace) o 7 / 8 del árbol (si hay dos), por lo que ya tiene la expectativa de buscar 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 las hojas.

Además, DFS es más fácil de implementar que BFS. Por lo tanto, es el que debe usar a menos que sepa algo sobre sus ciclos (por ejemplo, es probable que los ciclos estén cerca de la raíz desde la que busca, momento en el que BFS le da una ventaja).

Para demostrar que un gráfico es cíclico, solo necesita demostrar 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 comprobamos si tiene ciclo. Tan pronto como se encuentra un ciclo, podemos omitir la comprobación de otros vértices.

En BFS, necesitamos realizar un seguimiento de muchos bordes de vértices simultáneamente y la mayoría de las veces al final se descubre si tiene un ciclo. A medida que aumenta el tamaño del gráfico, BFS requiere más espacio, cálculo y tiempo en comparación con DFS.

Depende en cierto modo de si se trata de implementaciones recursivas o iterativas.

Recursive-DFS visita cada nodo dos veces. Iterative-BFS visita cada nodo una vez.

Si desea detectar un ciclo, debe investigar los nodos antes y 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 la gente elige Recursive-DFS.

Tenga en cuenta que una implementación simple de Iterative-DFS con, digamos, 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 "termina" con un nodo (respondido en el contexto de TopoSort):

Ordenación topológica usando DFS sin recursividad

Con suerte, eso explica por qué la gente prefiere Recursive-DFS para problemas en los que necesita determinar cuándo "termina" de procesar un nodo.

Deberá utilizarlo BFScuando desee encontrar el ciclo más corto que contenga un nodo determinado en un gráfico dirigido.

P.ej:

Si el nodo dado es 2, hay tres ciclos en los que forma parte de - [2,3,4], [2,3,4,5,6,7,8,9]& [2,5,6,7,8,9]. El más corto es[2,3,4]

Para implementar esto usando BFS, debe mantener explícitamente el historial de los nodos visitados utilizando estructuras de datos adecuadas.

Pero para todos los demás propósitos (por ejemplo: encontrar algún camino cíclico o comprobar si existe un ciclo o no), DFSes la opción clara por las razones mencionadas por otros.