Mi az mélységi keresés (DFS)?

Question

Accepted Answer

**DFS** egy gráfot úgy vizsgál, hogy minden ág mentén olyan mélyre megy, amennyire lehetséges, mielőtt visszalépne. Egy **stack**-et (gyakran a hívási stack-et rekurzióval) használ, és egy teljes útvonalat meglátogat, mielőtt alternatívákat fedezne fel.

## Az ötlet

Egy csomópontból recurse egy nem látogatott szomszédba, és folytassa mélyre; amikor beragad, lépjen vissza és próbálja meg egy másik ágat.

## Példa

```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 |
|---|-----|-----|
| Struktúra | queue | stack / recursion |
| Megtalál | legrövidebb (súlyozatlan) | bármely útvonal |
| Memória | O(V) frontier | O(depth) |
| Jó a | legrövidebb útvonal, szintek | ciklusok, topo sort, komponensek |

## Összetettség

- **Idő:** O(V + E). **Tér:** O(V) (rekurzió mélysége + meglátogatott).

## Csapdák

Mély gráfok túlcsordíthatják a rekurzív stack-et — használjon explicit stack-et. Nyomon kell követni a `visited`-et a ciklusok kezeléséhez.

## Miért fontos

A DFS alapja a ciklusdetektálásnak, topológiai rendezésnek, összekapcsolt komponenseknek és a labirintus/útvonal-generálásnak.

Rekurzív elegánsága tömörré teszi a fa- és gráf-kódot.

Annak tudása, hogy mikor jobbnak bizonyul a mélységi keresés, mint a szélességi keresés, alapvető gráf-algoritmus folyékonyság.

	BFS	DFS
Struktúra	queue	stack / recursion
Megtalál	legrövidebb (súlyozatlan)	bármely útvonal
Memória	O(V) frontier	O(depth)
Jó a	legrövidebb útvonal, szintek	ciklusok, topo sort, komponensek