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:
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!.
Aquí está mi recuento de bucles simples para mi problema de caso.
fuente
Respuestas:
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
El documento contiene un algoritmo completo.
fuente