Wat is diepte-eerst zoeken (DFS)?

Question

Accepted Answer

**DFS** onderzoekt een grafiek door zo diep mogelijk langs elke tak te gaan voordat het terugloopt. Het gebruikt een **stack** (vaak de call stack via recursie) en bezoekt een volledig pad voordat het alternatieven onderzoekt.

## Het idee

Van een knooppunt, recursief in een onbezochte buur; blijf diep gaan; wanneer vast, terug en probeer een andere tak.

## Voorbeeld

```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 versus DFS

| | BFS | DFS |
|---|-----|-----|
| Structuur | queue | stack / recursie |
| Vindt | kortste (ongewogen) | elk pad |
| Geheugen | O(V) grens | O(diepte) |
| Goed voor | kortste paden, niveaus | cycli, topo sort, componenten |

## Complexiteit

- **Tijd:** O(V + E). **Ruimte:** O(V) (recursie diepte + bezocht).

## Valkuilen

Diepe grafieken kunnen recursie stack overloop veroorzaken — gebruik een expliciete stack. Volg `visited` om cycli af te handelen.

## Waarom het belangrijk is

DFS ondersteunt cyclus detectie, topologische sortering, verbonden componenten en doolhof/padgeneratie.

Zijn recursieve elegantie maakt boom- en grafieken code beknopt.

Weten wanneer diepte-eerst beter is dan breedte-eerst is kernvaardigheid in grafiekalgoritmen.

	BFS	DFS
Structuur	queue	stack / recursie
Vindt	kortste (ongewogen)	elk pad
Geheugen	O(V) grens	O(diepte)
Goed voor	kortste paden, niveaus	cycli, topo sort, componenten