Encontre os ciclos simples em um gráfico direcionado

Este problema, para mim, parece muito interessante. Ele estava prestes a encontrar um ciclo simples (isto é, ciclo onde não há nós repetidos) em um gráfico direcionado.

Minha solução está sendo assim, ou seja, este gráfico é um problema de caso:

Eu sei que existe um ciclo em um gráfico, quando você pode encontrar "bordas traseiras" em uma pesquisa profunda (mostrada na minha foto no DFSTree) e, por um momento, posso garantir alguns ciclos, mas não por alguns. tudo, ciclos simples. Porque os egdes direcionados são tão importantes para um ciclo, ou seja (0123)! = (0321)

Estou pensando em fazer um DFS para cada nó com bordas traseiras, mas não tenho certeza e não está claro. Então, eu pergunto, se você me guiar. Obrigado!.

Aqui está a minha contagem de loops simples para o meu problema de caso.

Esta questão parece ser muito googleable. Por exemplo, você pode estar interessado no algoritmo apresentado neste documento:

Encontrando todos os circuitos elementares de um gráfico direcionado . Donald B. Johnson. SIAM J. COMPUT. Vol. 4, nº 1, março de 1975

Abstrato. É apresentado um algoritmo que encontra todos os circuitos elementares - de um gráfico direcionado no tempo limitado por O((n + e)(c + 1))e espaço limitado por O(n + e), onde existem nvértices, earestas e ccircuitos elementares no gráfico. O algoritmo se assemelha aos algoritmos de Tiernan e Tarjan, mas é mais rápido porque considera cada extremidade no máximo duas vezes entre qualquer circuito e o próximo na sequência de saída.

O artigo contém um algoritmo completo.