Was ist Tiefensuche (DFS)?

Question

Accepted Answer

**DFS** erforscht einen Graphen, indem es entlang jedes Zweigs so tief wie möglich vordringt, bevor es zurückweicht. Es verwendet einen **Stack** (oft den Call Stack über Rekursion) und besucht einen vollständigen Pfad, bevor es Alternativen erforscht.

## Die Idee

Von einem Knoten aus rekursiv in einen unbesuchten Nachbarn gehen und tief vordringen; wenn man steckenbleibt, zurückweichen und einen anderen Zweig versuchen.

## Beispiel

```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 |
|---|-----|-----|
| Struktur | queue | stack / recursion |
| Findet | kürzeste (ungewichtet) | jeden Pfad |
| Speicher | O(V) frontier | O(depth) |
| Gut für | kürzeste Pfade, Ebenen | Zyklen, topologische Sortierung, Komponenten |

## Komplexität

- **Zeit:** O(V + E). **Speicher:** O(V) (Rekursionstiefe + besucht).

## Fallstricke

Tiefe Graphen können den Rekursions-Stack überlasten — einen expliziten Stack verwenden. `visited` verfolgen, um Zyklen zu handhaben.

## Warum es wichtig ist

DFS liegt Zyklenerkennung, topologischer Sortierung, verbundenen Komponenten und Labyrinth-/Pfad-Generierung zugrunde.

Ihre rekursive Eleganz macht Baum- und Graph-Code prägnant.

Zu wissen, wann Tiefensuche Breitensuche schlägt, ist grundlegende Fähigkeit in Graph-Algorithmen.

	BFS	DFS
Struktur	queue	stack / recursion
Findet	kürzeste (ungewichtet)	jeden Pfad
Speicher	O(V) frontier	O(depth)
Gut für	kürzeste Pfade, Ebenen	Zyklen, topologische Sortierung, Komponenten