Witam. Mam do zrobienia pewne zadanie do którego potrzebne jest mi policzenie liczby cykli w grafie nieskierowanym a kompletnie nie mam pojęcia jak to zrobić. Graf zaimplementowany mam poprzez listę sąsiedztwa czyli tablica, której indeksy reprezentują każdy z wierzchołków i pod każdym indeksem jest lista z sąsiednimi wierzchołkami.
0
0
Filmik:
0
Tyle że bardziej chodzi mi o to jak sprawdzić ilość takich cykli a nie czy w ogóle istnieje. W moim przypadku funkcja sprawdzająca to miałaby zwrócić true jeżeli istnieje dokładnie 1 cykl.
0
A to mają być cykle proste czy złożone (z pętęlkami)?
Jak w grafie masz tylko cykle proste to robisz standardowego DFS do wykrycia cyklu, i po wykryciu cyklu nie przerywasz, tylko go dalej kontynujesz w poszukiwaniu kolejnego cyklu, i zliczasz ile cykli było po drodze.
Naatomiast zliczanie dowolnych cykli to już z tego co internet twierdzi to jest problem NP.
0
Tylko cykle proste
0
Do tego jest Trajan's strongly connected components algorithm. Z wyjścia oczywiście trzeba odrzucić pojedyncze wierzchołki.
0
Niektórzy argumentowali, że to jest to samo, tutaj coś co chyba opisuje Twój przypadek: http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf