Mam zrobić program znajdujący cykle w grafie skierowanym. Dowiedziałem się że można wykorzystać do tego DFS'a, ale nie wiem jak ;( ;(
Niby zrobiłem program, który to znajdował ale niestety nie wszystkie ;( ;(
Potem dowiedziałem się że DFS'a można wykorzystać tylko do grafów nieskierowanych.
Więc: Można to zrobić za pomocą DFS'a, jeśli tak to jak, jeśli nie to też jak??
Pomocy
Jak to tylko dla nieskierowanych? Właśnie tą metodę wykorzystuje się przy grafach skierowanych (a czy nieskierowanych, to nie wiem :) ). Wykonuje się dwóch przeszukiwań w głąb i nie ma problemu - polecam lekturę książki "Wprowadzenie do algorytmów".
PS. Znowu OI? :P Tym bardziej polecam tą lekturę lub inny ciekawy zbiór algorytmów.
na nieskierowanym każda droga będzie tworzyła cykl - bez sensu
gaborek napisał(a)
na nieskierowanym każda droga będzie tworzyła cykl - bez sensu
Niekoniecznie. Wystarczy pominąć ścieżkę do wierzchołka, z którego się przyszło.
wtedy szukamy cyklu eulera-szczegolny przypadek-inny algo :P
Dla każdego wierzchołka wywołaj algorytm przeszukiwania w głąb (jezeli algorytm 'wroci' do wierzcholka dla ktorego zostal wywolany to masz oczywiscie cykl) . Po skończeniu przeszukiwania dla danego wierzchołka usuń dany wierzchołek z grafu ( i wywolaj ten algorytm dla nastepnego wierzcholka).
kolega proponuje rozwiązanie kwadratowe- algo silnie spójnych składowych powinien wystarczyć - liniowe
przeszukiwaniem w głąb lecisz i zapisujesz kolejność przeglądanych wierzchołków, przelatujesz drugi rasz przeszukiwaniem ale w odwrotnej kolejności -według tego co sobie zapisałeś. i tam gdzie Ci sie zagłębia tam masz cykle.
ja nie wiem po co ten wątek sie tak wlecze dalej :|