efektívny algoritmus pre identifikáciu slučky v riadenom grafe? [duplikát] - algoritmus, graf, teória zložitosti, teória grafov, orientovaný graf

Možné duplicitné:
Najlepší algoritmus na detekciu cyklov v riadenom grafe

Hľadám algoritmus na nájdenie slučiek v nasmerovanom grafe.

Môj graf má štítky len v uzloch, nie v okrajoch, a môže to byť dosť obrovské.

Výstupom algoritmu by mali byť slučkyako súbor zoznamov, každý zoznam by mal obsahovať štítky uzlov zapojených do slučky, takže prvý a posledný prvok v zozname by mali byť rovnaké.

Grafy, ktoré používam, budú mať s najväčšou pravdepodobnosťou len jednu pripojenú zložku a žiadne silne spojené komponenty. Očakáva sa, že počet cyklov bude nízky (musím to ešte skontrolovať).

Akýkoľvek dobrý algoritmus pre presne toto alebo niečo podobné je vítaný.

Ďakujem mnohokrát.

PS: Ak niečo nie je jasné, neváhajte sa opýtať viac podrobností, napríklad graf je uložený (ako doteraz) ako súprava sád okrajov, od jedného uzla po niekoľko uzlov, zvyčajne jedného, ​​to by malo byť irelevantné, IMHO.

odpovede:

Podobná otázka bola položená a niekto poskytol veľmi podrobnú odpoveď, ktorá vám môže pomôcť - Nájdenie všetkých cyklov v priamom grafe