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.