Znajdź proste cykle na wykresie ukierunkowanym

15

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: wprowadź opis zdjęcia tutaj

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!. wprowadź opis zdjęcia tutaj

Oto moja liczba prostych pętli dla mojego problemu.

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutajwprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

jonaprieto
źródło
Znalazłem ten stackoverflow.com/questions/2939877/…
jonaprieto

Odpowiedzi:

13

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.

badroit
źródło
Dobrze. Papier jest idealny, ale czy mogę iść gdziekolwiek z moją pracą, czy po prostu poszukać papieru? Szukałem, abyś przedstawił mi rozwiązanie, czego zapominam ze swoim pomysłem?
jonaprieto,
2
Twoim głównym problemem jest to, że drzewo dfs nie jest unikalne (np. Zamień „1” na „3” na diagramie). Musisz spojrzeć na wszystkie możliwe drzewa DFS, aby policzyć wszystkie cykle.
badroit,
1
Jeśli potrzebujesz implementacji Java tego algorytmu: github.com/1123/johnson
user152468
@badroit link is broken ... :(
Jorge E. Hernández
@lalongooo, dzięki tak, zastąpiłem to.
badroit,