Overview
DFS erkundet einen Graphen in die Tiefe, bevor er zurückgeht – natürlich durch Rekursion oder expliziten Stack.
Analogy
Labyrinth erkunden: immer den ersten unbekannten Gang entlanggehen, bei Sackgasse zurückkehren.
Step-by-step
- Starte an Knoten s; markiere als besucht.
- Für jeden Nachbar v: wenn nicht besucht → rekursiver Aufruf dfs(v).
- Bei Rückkehr: alle Knoten im selben Teilbaum sind erkundet.
Visual
Graph 1-2-4, 1-3. DFS von 1: besuche 1→2→4 (zurück)→3; Reihenfolge: 1,2,4,3
Common mistakes
- Visited markieren vor dem rekursiven Aufruf – nicht danach (sonst Endlosschleife bei Zyklen).
- Python Rekursionslimit: bei tiefen Graphen iterativen DFS mit Stack verwenden.
Practice questions
- Zusammenhängende Komponenten zählen mit DFS.
- Zyklus in gerichtetem Graph mit DFS erkennen.
Space
O(V) Call-Stack oder expliziter Stack