Strona główna » Algorytmy » Artykuły » Wykrywanie Cykli
 

Wykrywanie Cykli

Cel

W grafach skierowanych może występować cykl czyli zamknięta ścieżka, która początek i koniec ma w tym samym wierzchołku. Do wykrycia cykli można skorzystać z algorytmu DFS do przeszukiwania grafu w głąb. W tym artykule zostanie wyjaśnione jak napisać taki algorytm.

Przykład

Poniżej został przedstawiony graf, który składa się z trzech składowych. Występują tutaj 3 różne cykle.

Przykładowe cykle

Istnieje tutaj cykl ABEFCA, który można uznać za jazdę pomiędzy różnymi miejscowościami i dotarciem do wierzchołka początkowego. Po prawej taki cykl został uproszczony do dwóch wierzchołków czyli podróż "tam i z powrotem". Na samym dole jest zdegenerowany cykl pomiędzy jednym i tym samym wierzchołkiem.

Usuwając niektóre krawędzi i dodając ewentualnie nowe można utworzyć graf w którym nie ma żadnego cyklu.

Graf bez cykli

Po usunięciu krawędzi FC nie istnieje już pierwszy wspomniany cykl. Oczywiście nie istnieje cykl BEFB, ponieważ BF musiałoby zostać skierowane w drugą stronę. Podobnie w grafie po prawej stronie. Na dole pozostał samotny wierzchołek bez pętli. Przez to na dole również znika cykl.

Implementacja
Część prywatna
Testowanie funkcji
Kod źródłowy ImplementacjaKod źródłowy ImplementacjaKod źródłowy Implementacja
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1