Witajcie. Poszukuję algorytmu grafowego znajdującego cykle i chyba nawet takowy znalazłem ale jest napisany wydaje mi się w C#. Chcę go przerobić na Javę ale nie bardzo rozumiem jak działa (i przy okazji nie znam C#). Wydaje mi się że jest w jakiś sposób oparty na przeszukiwaniu wszerz. Będę wdzięczny za pomoc w rozkminieniu go, najlepiej w jakiejś formie łatwej do implementacji (lista kroków etc.)
Pzdr.
I czego tutaj nie rozumiesz? Btw, jak możesz znać Jave i jednocześnie nie rozumieć kodu spod tego linka? (już pomijam sam algorytm...)
Składnia składnią są odpowiedniki w JAVIE. Ale ja ten alg muszę przerobić do swoich potrzeb, mam inną reprezentację grafu itp. dlatego muszę zrozumieć algorytm.
Nadal nie napisałeś z czym masz problem.
W Twojej sytuacji, szukanie gotowego kodu jest najgorszym z możliwych rozwiązań. Weź kartkę papieru i ołówek, narysuj sobie dowolny graf i spróbuj samodzielnie dojść do (bądź co bądź - trywialnego) algorytmu. Jeśli nie dajesz rady, poszukaj w sieci algorytmu. Podkreślam - algorytmu, a nie gotowego kodu. Gotowy kod będzie dla Ciebie jeszcze bardziej zawiły niż algorytm zapisany w postaci listy kroków, bo zawiera dokładną, szczegółową implementację dla konkretnej reprezentacji grafu, a nie ogólny zamysł.
Bardziej w temacie: odnajdywanie cykli w grafie to przejście po nim i zaznaczanie odwiedzanych wierzchołków. W momencie, gdy podczas przechodzenia napotkamy już wcześniej odwiedzony wierzchołek, wiemy, że znajduje się on na cyklu. Aby odtworzyć ścieżkę cyklu, wystarczy cofnąć się do momentu, gdy po raz pierwszy odwiedziliśmy ów podwójnie odwiedzony wierzchołek
Heh tyle co ja grafów narysowałem, algorytmów przetestowałem, naszukałem się po różnych talibańskich stronach, jedyne co działało to właśnie to. Mam to przerobione na JAVę ale zależy mi na zrozumieniu algorytmu. Pewnie w końcu go rozkmnię, nie wiem czy jest najoptymalniejszy ale działa.
No i jak ktoś wspomniał sprawdzenie czy w grafie istnieje cykl != wyszukaniu ich wszystkich! To zupełnie inne algorytmy, no może poza tym wspólnym mianownikiem jakim chyba jest DFS.