DFS

O(V + E)

Prohledávání do hloubky se zanoří po jedné cestě co nejhlouběji, pak se vrátí a zkusí další. Používá zásobník — tady zásobník volání (rekurze) — takže se jako první zpracuje naposledy objevený uzel (LIFO). DFS stojí za detekcí cyklů, topologickým řazením, řešením bludišť i hledáním komponent souvislosti.

Klik do prázdna = vrchol · klik na 2 vrcholy = hrana · táhni = posuňStart: A
Vstupní graf
Zásobník
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Vlož výchozí uzel na zásobník a navštiv ho.
  2. Z aktuálního uzlu přejdi na prvního nenavštíveného souseda a navštiv ho — vlož ho na zásobník.
  3. Když uzel nemá žádné nenavštívené sousedy, vyjmi ho a vrať se na předchozí.
  4. Opakuj, dokud není zásobník prázdný — pak jsou navštíveny všechny dosažitelné uzly.

Pseudokód

1DFS(graph, start):2  explore(start)34explore(node):5  visit(node); mark visited       # push a call frame6  for each neighbour of node:7    if neighbour not visited:8      explore(neighbour)           # recurse — go deep first9  # returning = pop the frame (backtrack)