V implementaci DFS můžeme místo zásobníku využít rekurze. Ta je ve skutečnosti implementována zase pomocí zásobníku, ale je příjemnější pro programátora. Abychom si ulehčili výklad, tak budeme během průchodu grafu barvit vrcholy. Vrcholy, které jsme ještě nenavštívili budou mít bílou barvu. Vrcholy, které zpracováváme (už jsme se do nich dostali, ale ještě jsme neprozkoumali všechny cesty z nich vedoucí) barvu šedou a hotové vrcholy barvu černou. Šedé jsou přesně ty vrcholy, které jsou na zásobníku.

V polích in[v] a out[v] si budeme pro každý vrchol pamatovat čas, kdy jsme do něj poprvé vstoupili a kdy jsme ho nadobro opustili.

Při praktickém použití není nutné rozlišovat všechny tři barvy, ani si pamatovat in[v] a out[v]. Stačí, když budeme schopni rozlišit, které vrcholy jsme už navštívili a které ještě ne.

Graf si reprezentujeme seznamem sousedů, takže seznam sousedi[v] je seznam sousedních vrcholů vrcholu $v$.

Projdi($v$):
	 color[$v$]=GREY
	 time=time$+1$
	 in[$v$]=time
	 foreach $w\in \mbox{Sousedi}[v]$    do
	 	if color[w]=WHITE then
	 		 Projdi($w$)
	 color[$v$]=BLACK
	 time=time$+1$
	 out[$v$]=time

Procedura Projdi($v$) projde tu část grafu, které je dosažitelná z výchozího vrcholu. Pokud by graf měl několik oddělených částí, tak musíme do každé části převézt Thesea helikoptérou. Postupně v každé části zvolíme výchozí místo a z něj graf projdeme. To obstará následující procedura DFS.

DFS():
	 $\forall v\in V\,:$ color[$v$]=WHITE
	 time=$0$
	 foreach $v\in V$  do
	 	if color[$w$]=WHITE then
	 		 Projdi($w$)

Podívejme se nejprve na tu část grafu, kterou jsme prošli procedurou Projdi(v). Výchozí vrchol $v$ nazveme kořen. Hrany, po kterých jsme v průběhu algoritmu prošli do nenavštíveného bílého vrcholu tvoří strom. Proto tyto hrany nazveme stromové a jim odpovídající strom nazveme DFS stromem (stromem průchodu do hloubky). Ostatním hranám budeme říkat zpětné, protože vedou zpět do již navštívených vrcholů. Stromy průchodu všech oddělených částí dohromady tvoří DFS les.

Pokud při prozkoumávání vrcholu $v$ projdeme stromovou hranou do vrcholu $u$, tak řekneme, že $u$ je synem $v$. Naopak $v$ je otcem $u$. Všechny synové vrcholu $v$, synové synů a tak dále jsou potomci vrcholu $v$. Obráceně se dá říci, že $v$ je jejich předchůdce. Někdy místo potomci říkáme následníci. Ještě jednou a přesněji, $u$ je následník vrcholu $v$ v zakořeněném stromě, pokud $v$ leží na jednoznačné cestě z kořene do $u$.

Na obrázku budeme syny každého vrcholu kreslit pod jejich otce a v pořadí zleva doprava tak, jak jsme na ně při průchodu do hloubky narazili.

Příklad: Na následujícím obrázku vlevo je graf $G$, který projdeme pomocí DFS. Pokaždé, když si algoritmus můžete vybrat z několika vrcholů, tak vybereme abecedně nejmenší vrchol. Na obrázku vpravo je strom průchodu grafu $G$ do hloubky. Čísla u každého vrcholu $v$ jsou hodnoty in[v], out[v], tj. časy příchodu a odchodu. Zkuste si sami odkrokovat průběh algoritmu.