Znajdź proste cykle na wykresie ukierunkowanym

Dla mnie ten problem wygląda bardzo interesująco. Już miał znaleźć prosty cykl (tj. Cykl, w którym nie ma powtarzalnych węzłów) na ukierunkowanym wykresie.

Moje rozwiązanie wygląda następująco, tzn. Ten wykres jest problemem przypadku:

Wiem, że na wykresie jest cykl, w którym można znaleźć „tylne krawędzie” w wyszukiwaniu z głębokością pierwszą (przerywaną na moim zdjęciu w DFSTree) i przez chwilę mogę się upewnić przez kilka cykli, ale nie dla wszystkie proste cykle. Ponieważ ukierunkowane egdes tak ważne dla cyklu, tj. (0123)! = (0321)

Myślę o zrobieniu dfs dla każdego węzła z tylnymi krawędziami, ale nie jestem pewien i to nie jest jasne. Pytam więc, czy mnie poprowadzisz. Dzięki!.

Oto moja liczba prostych pętli dla mojego problemu.

To pytanie wydaje się być bardzo Googleable. Na przykład możesz być zainteresowany algorytmem przedstawionym w tym artykule:

Znajdowanie wszystkich obwodów elementarnych ukierunkowanego wykresu . Donald B. Johnson. SIAM J. COMPUT. Vol. 4, nr 1, marzec 1975 r

Abstrakcyjny. Przedstawiony jest algorytm, który znajduje wszystkie obwody elementarne ukierunkowanego wykresu w czasie ograniczonym O((n + e)(c + 1))i przestrzeni ograniczonej przez O(n + e), gdzie na wykresie znajdują się nwierzchołki, ekrawędzie i cobwody elementarne. Algorytm przypomina algorytmy Tiernana i Tarjana, ale jest szybszy, ponieważ bierze pod uwagę każdą krawędź maksymalnie dwa razy między jednym obwodem a następnym w sekwencji wyjściowej.

Artykuł zawiera pełny algorytm.