Cómo detectar un ciclo en un gráfico dirigido

En términos simples

Esto no es diferente al caso de: Comenzaste a llegar a algún lado, pero llegaste a un punto intermedio que ya has alcanzado antes.

Para saber si volvió a alcanzar un punto intermedio, todo lo que tiene que hacer es marcarlo, decir si llegó a un área y marcarlo con una tiza o sobre una piedra. Cuando viaje más lejos para llegar a destino, suponga que volvió a llegar a un área marcada anteriormente, sabe que ha detectado / detectado un ciclo. Puedes usar cualquiera de los recorridos del árbol. La mayoría de las suposiciones son: cualquiera de los DFS lo llevará rápidamente al destino o detectará un ciclo. BFS también puede detectar el ciclo si marca / recuerda un nodo atravesado como visitado.

Espero que haya ayudado.

La mejor de las suertes

Se puede utilizar un primer recorrido de profundidad (DFS) del árbol para detectar un ciclo en un gráfico dirigido.

Cuando se aplica DFS sobre un gráfico dirigido y conectado, producirá un árbol. Si el árbol contiene un borde posterior, podemos decir que el gráfico tiene un ciclo presente.

Más explicación en el borde posterior : suponga que el nodo ‘v’ en un antecesor del nodo ‘u’ en un árbol. Se dice que un borde (u, v) es un borde posterior. Básicamente, un borde posterior es un borde que es desde un nodo hacia sí mismo (auto loop) o hacia un antepasado.

En este caso, los tres bordes posteriores (marcados con ‘x’) denotan la presencia de tres ciclos en el gráfico dado.

Más : detectar ciclo en un gráfico dirigido – GeeksforGeeks

Detectar ciclo en un gráfico dirigido

Dado un gráfico dirigido, verifique si el gráfico contiene un ciclo
o no. Su función debe devolver verdadero si el gráfico dado contiene
al menos un ciclo, de lo contrario, devuelve falso.

por
ejemplo, el siguiente gráfico contiene tres ciclos 0-> 2-> 0,
0-> 1-> 2-> 0 y 3-> 3, por lo que su función debe devolver verdadero.

Solución

La profundidad del primer recorrido se puede utilizar para detectar el ciclo en un gráfico. DFS para un
El gráfico conectado produce un árbol. Hay un ciclo en un gráfico solo si
hay un borde trasero
presente en el gráfico. Un borde posterior es un borde que es de un nodo a
sí mismo (selfloop) o uno de sus antepasados ​​en el árbol producido por DFS. En
En el siguiente gráfico, hay 3 bordes posteriores, marcados con un signo de cruz. Nosotros
puede observar que estos 3 bordes posteriores indican 3 ciclos presentes en el
grafico.

Para un gráfico desconectado, obtenemos el DFS forrest como salida. Detectar
ciclo, podemos verificar el ciclo en árboles individuales volviendo a verificar
bordes

Para detectar un borde posterior, podemos hacer un seguimiento de los vértices actualmente en
pila de funciones de recursión para el recorrido DFS. Si alcanzamos un vértice
que ya está en la pila de recursión, luego hay un ciclo en el
árbol. El borde que conecta el vértice actual al vértice en el
la pila de recursión está en el borde posterior. Hemos utilizado la matriz recStack [] para mantener
seguimiento de vértices en la pila de recursión.

Según lo explicado por Shashi, una búsqueda en profundidad (DFS) es una solución; sin embargo, asegúrese de aplicar su DFS en el componente conectado en el que sería dicho ciclo. Por ejemplo, si su gráfico consiste en un ciclo + un vértice aislado, no desea aplicar su DFS a partir del vértice aislado …

¿Pero qué vértice elegirías si tu gráfico no está conectado?

Una solución brutal es probar cada vértice. Sin embargo, eso aumentaría enormemente la complejidad, especialmente en el caso de un gráfico ya conectado.

La solución es marcar cada vértice que visita durante DFS y aplicar su DFS solo a partir de vértices sin marcar.

Además, tenga en cuenta que esto solo se aplica al gráfico no dirigido. Si desea detectar un ciclo en un gráfico dirigido, una forma simple de hacerlo es verificar la inexistencia de una clasificación topográfica (consulte Clasificación topológica)

Mira esta explicación con visualizaciones. También tiene código Java y Python.

Detectar ciclo en gráfico dirigido

Otro enfoque simple podría ser utilizar la clasificación topológica. Si pudiera encontrar el tipo topológico de la gráfica, entonces no hay ciclo. Lea sobre el algoritmo de Kahn a continuación

Clasificación topológica

Al aplicar la primera búsqueda de profundidad (dfs) al gráfico, si obtenemos un borde posterior, podemos decir que el gráfico dado contiene al menos un ciclo.
* borde posterior: (u, v) es un borde, si visitamos el árbol y encontramos que el nodo v se visita dos veces, entonces (u, v) se llama BACK EDGE. El gráfico contiene un ciclo.