Co je hloubkové prohledávání (DFS)?

Question

Accepted Answer

**DFS** prozkoumává graf tak, že jde co nejhlouběji podél každé větve, než se vrátí. Používá **zásobník** (často zásobník volání prostřednictvím rekurze) a navštíví celou cestu, než zkoumá alternativy.

## Myšlenka

Z uzlu se rekurzivně přejde do nenavštíveného souseda a pokračuje se hlouběji; když se zacyklí, vrátí se a zkusí další větev.

## Příklad

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS vs DFS

| | BFS | DFS |
|---|-----|-----|
| Struktura | fronta | zásobník / rekurze |
| Nalezneme | nejkratší (bez vah) | libovolnou cestu |
| Paměť | O(V) hranice | O(hloubka) |
| Vhodné pro | nejkratší cesty, úrovně | cykly, topologické třídění, komponenty |

## Složitost

- **Čas:** O(V + E). **Prostor:** O(V) (hloubka rekurze + navštívené).

## Běžné chyby

Hluboké grafy mohou způsobit přetečení zásobníku rekurze — použijte explicitní zásobník. Sledujte `visited` pro zpracování cyklů.

## Proč to je důležité

DFS je základem detekce cyklů, topologického třídění, souvislých komponent a generování bludišť/cest.

Její rekurzivní elegance činí kód stromů a grafů stručným.

Vědět, kdy je hloubkové prohledávání lepší než šírkové, je základní znalostí algoritmů grafů.

	BFS	DFS
Struktura	fronta	zásobník / rekurze
Nalezneme	nejkratší (bez vah)	libovolnou cestu
Paměť	O(V) hranice	O(hloubka)
Vhodné pro	nejkratší cesty, úrovně	cykly, topologické třídění, komponenty