10.3. Mélységi keresés

Mélységi keresés során az utoljára elért, új kivezető élekkel rendelkező csúcsok éleit derítjük fel. Ha az összes kivezető élt felderítettük, akkor a csúcs szülőjének kivezető éleit vizsgálja tovább az algoritmus. Ezt addig folytatjuk, míg a kiinduló csúcsból elérhető összes csúcsot fel nem derítettük. Ezek után a még fel nem derített csúcsok közül választunk egyet, s megkeressük az innen elérhető csúcsokat. Ezt ismételjük mindaddig, amíg az összes csúcsot fel nem fedeztük. Mikor a bejárás során szürkére festjük a csúcsot, az időpontot a pont be változójában tároljuk. A pont feketére festésének időpontját pedig ki változójában tároljuk. A három szín szerepe megegyezik a szélességi keresés színeinek szerepével.

Procedure MÉLYSÉGI-KERESÉS(G) 
Input: G gráf 
Eredmény: a gráf alapján egy erdőt generál 
1  forall the u ∊ V do 
2     u.szín = FEHÉR 
3     u.apa = Nil 
4  endfall 
5  idő = 0 
6  forall the u ∊ V do 
7     if u.szín == FEHÉR then 
8        MÉLYSÉGI-BEJÁR(u) 
9     endif
10 endfall 

Procedure MÉLYSÉGI-BEJÁR(u) 
Input: u csúcs 
Eredmény: a csúcsból elérhető, még fel nem derített csúcsok alapján felépít egy fát 
1  u.szín = SZÜRKE 
2  u.be = idő 
3  idő = idő + 1 
4  forall the v ∊ Adj(u) do 
5     if v.szín == FEHÉR then 
6        v.apa = u 
7        MÉLYSÉGI-BEJÁR(v) 
8     endif 
9  endfall 
10 u.szín = FEKETE 
11 u.ki = idő 
12 idő = idő + 1