DFS — Tiefensuche einfach erklärt

Depth-First Search, kurz DFS, ist ein Algorithmus zum Durchsuchen eines Baums oder Graphen, bei dem man einem Pfad so weit wie möglich folgt, bevor man zurückgeht. Einfach gesagt: DFS geht immer tiefer, bis es nicht mehr weiterkommt, und kehrt dann zur letzten Stelle zurück, an der noch ein anderer Zweig offen ist.

Wenn du dir nur eine Idee merkst, dann diese: DFS bedeutet „geh tief, dann geh zurück“.

Was die Tiefensuche macht

DFS kann auf Bäumen und auf allgemeinen Graphen verwendet werden. Ausgehend von einem Startknoten geht der Algorithmus wiederholt zu einem noch nicht besuchten Nachbarn. Erreicht er einen Knoten, bei dem keine unbesuchten Nachbarn mehr übrig sind, geht er zum vorherigen Knoten zurück und macht von dort weiter.

Dieses Zurückgehen ist das entscheidende Merkmal. In rekursiven Implementierungen übernimmt der Aufrufstapel das automatisch. In iterativen Implementierungen übernimmt ein expliziter Stack dieselbe Rolle.

Warum sich die DFS-Reihenfolge ändern kann

DFS erzeugt keine eine feste, universelle Besuchsreihenfolge. Die genaue Reihenfolge hängt davon ab, in welcher Reihenfolge die Nachbarn betrachtet werden.

Wenn ein Knoten zum Beispiel die Nachbarn $B$ und $C$ hat, kann ein Besuch von $B$ zuerst zu einer anderen DFS-Reihenfolge führen als ein Besuch von $C$ zuerst. In beiden Fällen ist es trotzdem DFS, denn die Regel bleibt gleich: erst tiefer gehen, bevor ein benachbarter Zweig untersucht wird.

DFS-Beispiel auf einem kleinen Graphen

Angenommen, der Graph hat diese Verbindungen:

• $A$ ist mit $B$ und $C$ verbunden
• $B$ ist mit $D$ und $E$ verbunden
• $C$ ist mit $F$ verbunden

Nehmen wir an, wir betrachten Nachbarn immer von links nach rechts und starten bei $A$.

Dann läuft DFS so ab:

1. Besuche $A$
2. Gehe zu $B$
3. Gehe zu $D$
4. $D$ hat keinen unbesuchten Nachbarn mehr, also gehe zurück zu $B$
5. Von $B$ aus gehe zu $E$
6. $E$ ist fertig, also gehe zurück zu $B$ und dann zu $A$
7. Von $A$ aus gehe zu $C$
8. Von $C$ aus gehe zu $F$

Eine mögliche gültige DFS-Besuchsreihenfolge ist also:

$$A, B, D, E, C, F$$

Die zentrale Idee ist, dass DFS die Seite $A \to B$ vollständig abarbeitet, bevor es mit der Seite $A \to C$ beginnt. Wenn du die Reihenfolge der Nachbarn änderst, kann sich auch die Besuchsreihenfolge ändern.

Warum Backtracking einen Stack verwendet

DFS braucht immer eine Möglichkeit, sich zu merken, wohin es nach einer Sackgasse zurückkehren muss. Deshalb tauchen Stacks bei DFS ganz natürlich auf.

Bei rekursivem DFS wartet jeder Funktionsaufruf, während die Suche tiefer geht, und das Programm kehrt beim Backtracking in umgekehrter Reihenfolge zurück. Bei iterativem DFS legst du Knoten auf einen Stack und nimmst sie wieder herunter, wenn du vom zuletzt noch nicht vollständig bearbeiteten Punkt aus weitermachen musst.

Zeit- und Speicherkomplexität von DFS

Wenn der Graph als Adjazenzliste gespeichert ist und jeder Knoten beim ersten Besuch markiert wird, dann läuft DFS für den erreichbaren Teil des Graphen in

$$O(V + E)$$

Zeit, wobei $V$ die Anzahl der Knoten und $E$ die Anzahl der Kanten ist.

Der zusätzliche Speicherbedarf ist typischerweise

$$O(V)$$

weil sowohl die Besuchsmarkierungen als auch der Rekursionsstack oder der explizite Stack mit der Anzahl der Knoten wachsen können.

Häufige DFS-Fehler

Vergessen, besuchte Knoten zu markieren

In einem allgemeinen Graphen kann DFS ohne Besuchsprüfung in einem Zyklus unendlich weiterlaufen. Selbst in einem Baum, der als ungerichteter Graph gespeichert ist, musst du vermeiden, sofort zum Elternknoten zurückzugehen, außer dein Code behandelt diesen Fall ausdrücklich.

Annehmen, dass DFS den kürzesten Pfad findet

DFS kann einen Pfad finden, garantiert aber im Allgemeinen keinen kürzesten Pfad in einem ungewichteten Graphen. Wenn der kürzeste Pfad das Ziel ist und alle Kanten gleiches Gewicht haben, ist BFS meist der bessere Ausgangspunkt.

Die DFS-Reihenfolge als eindeutig behandeln

Die Reihenfolge hängt von der Reihenfolge der Nachbarn ab. Wenn sich diese ändert, kann sich auch die Traversierungsreihenfolge ändern.

Wann Tiefensuche verwendet wird

DFS ist nützlich, wenn du Strukturen erkunden willst und nicht einfach nur zuerst die kleinste Entfernung. Häufige Anwendungen sind:

• prüfen, ob ein Knoten erreichbar ist
• zusammenhängende Komponenten finden
• Zyklen in bestimmten Graphen erkennen
• Bäume traversieren
• Backtracking-Probleme wie Labyrinthe oder Puzzlesuchen lösen

Der Hauptgrund, warum DFS so oft vorkommt, ist, dass „geh tief, dann geh zurück“ zu vielen rekursiven Problemstrukturen passt.

DFS vs. BFS: der praktische Unterschied

DFS geht zuerst einen Zweig hinunter. BFS untersucht zuerst alle Knoten in einer bestimmten Entfernung, bevor es zur nächsten Entfernung übergeht.

Wenn dir vollständige Erkundung oder rekursive Struktur wichtig ist, ist DFS oft naheliegend. Wenn du den kürzesten Pfad in einem ungewichteten Graphen suchst, ist BFS oft die sicherere erste Wahl.

Probiere eine ähnliche Traversierung aus

Zeichne einen kleinen Graphen mit sechs Knoten und lege eine feste Reihenfolge der Nachbarn fest. Führe DFS von Hand aus und notiere genau, wann du vorwärts gehst und wann du zurückgehst. Wenn sich deine Reihenfolge nach dem Umordnen der Nachbarn ändert, ist das kein Fehler. Genau so funktioniert DFS.