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.
algorithms
graphs
enumeration
jonaprieto
źródło
źródło
Odpowiedzi:
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
Artykuł zawiera pełny algorytm.
źródło