Parcurgerea în adâncime a grafurilor orientate

Parcurgerea în adâncime a grafurilor orientate

Se pune conditia de parcurgere a vecinilor oricarui nod, indiferent de sens. Parcurgerea în adâncime se caracterizează prin faptul că se merge „în adâncime” ori de câte ori este posibil. 

 Parcurgerea începe cu vâful iniţal, denumit vâful de start, care este şi vizitat. 
 Se vizitează apoi primul vecin nevizitat al vâfului de start. Vârful y este considerat vecin al vâfului x dacă există arcul (x,y) (pentru graful orientat). 

Se vizitează în continuare primul vecin nevizitat al primului vecin al vâfului de start, şi aşa mai departe, mergând în adâncime, până când ajungem într-un vârf care nu mai are vecini nevizitaţi. Când ajungem într-un astfel de vârf, revenim la vârful său părinte (vârful din care acest nod a fost vizitat). Dacă acest nod mai are vecini nevizitaţ, alegem primul vecin nevizitat al său şi continuă parcurgerea în acelaşi mod. Dacă nici acest vârf nu mai are vecini nevizitaţi, revenim în vârful să păirnte şi continuăm în acelaş mod, până când toate vâfurile accesibile din vârful de start sunt vizitate.