Prohledávání do hloubky: Porovnání verzí
Smazaný obsah Přidaný obsah
→Popis algoritmu: Přeformulováno pro lepší čitelnost. |
|||
Řádek 72:
=== Zjištění acykličnosti grafu ===
Pro zjištění acykličnosti grafu přidáme do algoritmu podmínku, zda byla nalezena zpětná hrana, tj. hrana, která vede do vrcholu ve stavu OPEN. Zpětná hrana spolu s jednou nebo několika hranami stromovými tvoří cyklus. Pokud se při prohledávání do hloubky žádná zpětná hrana nevyskytne, je graf acyklický.
== Složitost algoritmu ==
| |||