Prohledávání do hloubky

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|).

Související