Pseudokód
Každý vrchol se může nacházet v jednom z následujících stavů: {FRESH, OPEN, CLOSE}
. Potřebujeme odlišit navštívené a nenavštívené vrcholy. Na počátku označíme všechny stavy jako FRESH
(nenavštívený).
DFS využívá rekurzi a lze jej tedy snadno přepsat na iterační s uživatelským zásobníkem, kde otevření vrcholu znamená vložení na zásobník a uzavření vrcholu jeho vyjmutí ze zásobníku.
Inicializace
stavy := {FRESH, OPEN, CLOSE}
Pro každý vrchol u ∈ V(G):
stav(u) := FRESH
Algoritmus
Algoritmus DFS(vrchol v):
Když stav(v) není FRESH
return
stav(v) := OPEN
Pro každého souseda u vrcholu v:
DFS(u)
stav(v) := CLOSE
Časová složitost
Algoritmus DFS má při reprezentaci grafu seznamem sousedů časovou složitost O(|V|+|E|).
Paměťová složitost
Reprezentaci grafu seznamem sousedů paměťovou složitost O(|V | + |E|).
Důkaz
Hloubka zanoření rekurze je nejvýše |V|, čili systémový zásobník zabere maximálně O(|V|) paměti. Celkem tedy O(|V| + |E|).