Mikä on syvyyssuuntainen haku (DFS)?

Question

Accepted Answer

**DFS** tutkii graafia menemällä niin syvälle kuin mahdollista jokaisen haaran mukaisesti ennen kuin perääntyy. Se käyttää **pinoa** (usein kutsupinoa rekursion kautta) ja vierailee täydessä polulla ennen vaihtoehtojen tutkimista.

## Idea

Solmusta käsin recursoidaan vierailemattomaan naapuriin ja jatketaan syvälle; kun jumiin jää, peräännetään ja yritetään toista haaraa.

## Esimerkki

```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 |
|---|-----|-----|
| Rakenne | jono | pino / rekursio |
| Löytää | lyhin (painottamaton) | mikä tahansa polku |
| Muisti | O(V) raja | O(syvyys) |
| Hyvä | lyhyimmät polut, tasot | syklit, topologinen järjestys, komponentit |

## Kompleksisuus

- **Aika:** O(V + E). **Tila:** O(V) (rekursiosyvyys + vierailla oleva).

## Sudenkuopat

Syvät graafit voivat ylivuotaa rekursiopinon — käytä eksplisiittistä pinoa. Seuraa `visited`-tilaa syklien käsittelyyn.

## Miksi sillä on merkitystä

DFS on perustana syklien havaitsemiselle, topologiselle järjestykselle, yhteydessä oleville komponenteille ja labyrintin/polun luomiselle.

Sen rekursiivinen eleganssi tekee puu- ja graafkoodista ytimekkää.

Tietäminen, milloin syvyyssuuntainen haku voittaa leveyssuuntaisen haun, on graafialgoritmien ydinosaamista.

	BFS	DFS
Rakenne	jono	pino / rekursio
Löytää	lyhin (painottamaton)	mikä tahansa polku
Muisti	O(V) raja	O(syvyys)
Hyvä	lyhyimmät polut, tasot	syklit, topologinen järjestys, komponentit