Jest jakiś algorytm, którym będę mógł znaleźć wszystkie cykle w grafie skierowanym? Metoda z dfs-em i sprawdzaniem czy wierzchołek, w którym jesteśmy nie został już odwiedzony (i nie jest rodzicem aktualnego) nie rozwiązuje w pełni problemu ponieważ nie znajduje on wszystkich cykli. Dla przykładu, jak mam graf:
A |-B-C
B |-A-D
C |-A-D-E
D |-B-E
E |-C
To chciałbym aby odnalezione zostały cykle: A-B-C-A, B-C-D-B, C-D-E-C, A-B-D-E-C-A
Zacznij od znalezienia wszystkich http://pl.wikipedia.org/wiki/Sk%C5%82adowa_silnie_sp%C3%B3jna
A potem nie wiem, nie chce mi się wymyślać :P
1.Znajdź wszystkie silnie spójne, bo tylko w silnych istnieją cykle (dość proste do udowodnienia, bo jeśli idąc z jakiegoś wierzchołka przez inne silnie spójne(przechodząc przez wierzchołek x) z powrotem do niego, to wierzchołek x możemy "zamienić" z wierzchołkiem z jego spójnej, analogicznie dla każdego wierzchołka w każdej spójnej - to powinna być jedna spójna, czyli sprzeczność)
2.Dla każdej silnie spójnej trzeba cofać się Bfs'em bez zapamiętywania odwiedzonych nie dalej niż na rozmiar silnej. Jeśli trafimy na źródło naszego Bfs to zwracamy cykl.
Ten algorytm jest strasznie wolny, ale na pewno poprawny. Zwraca zduplikowane cykle, ale to można łatwo wykryć. Później spróbuję go przyspieszyć.
edit
Mam algorytm liniowy o(n*m) względem ilości cykli w grafie.
Jak wyszukiwać wszystkie ścieżki z b do a?
1.Zapuszczam dfs na grafie z wierzchołka b wyznacząjąc dla każdego wierzchołka wszystkich jego ojców(vector)
2.Tworzę funkcję f(x,y,cykl):
-jeśli (x==y) cykle.push_back(cykl+y);
-inaczej foreach(ojcowe[x] jako a)f(a,y,cykl+a)
3.Wywoluje tą funkcję f(a,b,""), ktora dodaje wszystkie cykle do vectora cykle
Jeśli coś jest źle to śmiało poprawiajcie
Wszystko dobrze, ale na pewno nie jest liniowy tylko gorzej.
_13th_Dragon napisał(a):
Wydzielasz z grafu minimalne drzewo rozpinające.
- Każda krawędź która nie weszła do drzewa rozpinającego zamyka cykl.
- Dowolna kombinacja ze znalezionych cykli w kroku 2 tworzy kolejny cykl o ile jest spełniony prosty warunek: każda para wchodząca w grupę ma przynajmniej jedną wspólną krawędź. (to nie sprawdzałem możliwe że warunek nie wystarczający)
Załóżmy, że mam już wyznaczone takie minimalne drzewo rozpinające. Załóżmy, że cykl zamyka krawędź 0-2. Czy wystarczy, że uruchomię na tym drzewie coś w rodzaju DFSa (według mnie się nada), który będzie przechodził drzewo od wierzchołka 0 aż dojdzie do wierzchołka 2? Wtedy cyklem będzie trasa przejścia + krawędź 0-2. Czy ten sposób jest poprawny? Jeśli nie, lub jest sposób efektywniejszy to jak to wykonać?
Biały Lew napisał(a):
_13th_Dragon napisał(a):
Wydzielasz z grafu minimalne drzewo rozpinające.
- Każda krawędź która nie weszła do drzewa rozpinającego zamyka cykl.
- Dowolna kombinacja ze znalezionych cykli w kroku 2 tworzy kolejny cykl o ile jest spełniony prosty warunek: każda para wchodząca w grupę ma przynajmniej jedną wspólną krawędź. (to nie sprawdzałem możliwe że warunek nie wystarczający)
Załóżmy, że mam już wyznaczone takie minimalne drzewo rozpinające. Załóżmy, że cykl zamyka krawędź 0-2. Czy wystarczy, że uruchomię na tym drzewie coś w rodzaju DFSa (według mnie się nada), który będzie przechodził drzewo od wierzchołka 0 aż dojdzie do wierzchołka 2? Wtedy cyklem będzie trasa przejścia + krawędź 0-2. Czy ten sposób jest poprawny? Jeśli nie, lub jest sposób efektywniejszy to jak to wykonać?
PS. Tak, DFS służy to przechodzenia grafów, ale chodzi mi o koncepcje.
Biały Lew napisał(a):
Załóżmy, że mam już wyznaczone takie minimalne drzewo rozpinające. Załóżmy, że cykl zamyka krawędź 0-2. Czy wystarczy, że uruchomię na tym drzewie coś w rodzaju DFSa (według mnie się nada), który będzie przechodził drzewo od wierzchołka 0 aż dojdzie do wierzchołka 2? Wtedy cyklem będzie trasa przejścia + krawędź 0-2. Czy ten sposób jest poprawny? Jeśli nie, lub jest sposób efektywniejszy to jak to wykonać?
Tak, jak najbardziej, ale radziłbym jednak nie DFS tylko jeden z: