Găsirea unui ciclu

Ideea găsirii unui ciclu este una simplă, dar cu o deosebită însemnătate în probleme: dacă la o parcurgere a grafului, din nodul curent ajungem într-un nod deja vizitat (diferit de cel din care l-am vizitat pe cel curent), decidem că în graf se găsește un ciclu. Muchia dintre nodul curent și cel vizitat se află pe ciclu. Justificare: în nodul curent s-a ajuns din rădăcină, dar și în cel vizitat s-a ajuns din rădăcină, anterior. Așadar muchia dintre cele două noduri devine o altă variantă de a ajunge între ele (cealaltă este fie prin intermediul rădăcinii, de care sunt legate ambele, fie prin alt strămoș comun al lor în arborele de acoperire - mai aproape de ele decât rădăcina).