Encuentra los ciclos simples en un gráfico dirigido

15

Este problema, para mí, parece muy interesante. Estaba a punto de encontrar un ciclo simple (es decir, ciclo donde no hay nodos repetidos) en un gráfico dirigido.

Mi solución es así, es decir, este gráfico es un problema de caso: ingrese la descripción de la imagen aquí

Sé que hay un ciclo en un gráfico, cuando puedes encontrar "bordes traseros" en una búsqueda de profundidad primero (discontinua en mi imagen en DFSTree), y por un momento puedo estar seguro por algunos ciclos, pero no por todos, ciclos simples. Porque, los egdes dirigidos son tan importantes para un ciclo, es decir (0123)! = (0321)

Estoy pensando en hacer un dfs para cada nodo con bordes posteriores, pero no estoy seguro, y no está claro. Entonces, te pregunto si me guías. ¡Gracias!. ingrese la descripción de la imagen aquí

Aquí está mi recuento de bucles simples para mi problema de caso.

ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquíingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí

jonaprieto
fuente
Encontré este stackoverflow.com/questions/2939877/…
jonaprieto

Respuestas:

13

Esta pregunta parece ser muy googleable. Por ejemplo, puede estar interesado en el algoritmo presentado en este documento:

Encontrar todos los circuitos elementales de un gráfico dirigido . Donald B. Johnson. SIAM J. COMPUT. Vol. 4, N ° 1, marzo de 1975

Resumen. Se presenta un algoritmo que encuentra todos los circuitos elementales de un gráfico dirigido en el tiempo limitado por O((n + e)(c + 1))y el espacio limitado por O(n + e), donde hay nvértices, ebordes y ccircuitos elementales en el gráfico. El algoritmo se parece a los algoritmos de Tiernan y Tarjan, pero es más rápido porque considera cada borde como máximo dos veces entre cualquier circuito y el siguiente en la secuencia de salida.

El documento contiene un algoritmo completo.

badroit
fuente
Okay. El papel es perfecto, pero ¿puedo ir a cualquier parte con mi trabajo o simplemente mirar el papel? Estaba buscando para presentarme la solución, ¿qué estoy olvidando con mi idea?
jonaprieto
2
Su principal problema es que el árbol dfs no es único (por ejemplo, cambie "1" con "3" en su diagrama). Tendría que mirar todos los árboles dfs posibles para enumerar todos los ciclos.
badroit
1
En caso de que necesite una implementación Java de este algoritmo: github.com/1123/johnson
user152468
El enlace @badroit está roto ... :(
Jorge E. Hernández
@lalongooo, gracias, sí, lo reemplacé.
badroit