DFS und Rekursion

DFS geht in die Tiefe: Rekursion oder expliziter Stack. Nützlich für Zusammenhang, Zykelsuche und topologische Sortierung in DAGs.

Markiere Knoten als besucht, sonst Endlosschleifen in Zyklen.

$$O(|V|+|E|)$$

Wo gebraucht

Zyklenerkennung, topologisches Sortieren, Connected Components, Maze-/Constraint-Suche, Compiler-Call-Graphen. Oft mit explizitem Stack statt tiefer Rekursion.

Vertiefung

Die Tiefensuche verfolgt einen noch offenen Zweig so weit wie möglich und kehrt danach zum letzten Verzweigungspunkt zurück. Rekursion speichert diesen Rückkehrzustand implizit in den Aktivierungsdatensätzen.

Ein Zustandsfeld pro Knoten verhindert erneute Expansion und macht Zyklen beherrschbar. Mit mehreren Zuständen lassen sich noch aktive von vollständig abgeschlossenen Knoten unterscheiden, was etwa Zyklenerkennung in gerichteten Graphen ermöglicht.

Ein- und Austrittszeiten erzeugen eine Klammerstruktur für verschachtelte Teilbäume. Darauf beruhen topologische Sortierung, Zusammenhangsanalysen und Klassifikation von Kanten.

Schwierigkeitsstufen

1. Rekursive Suchfolge für geordnete Nachbarn verfolgen.
2. Aktiv- und abgeschlossen-Zustand zur Zyklenerkennung nutzen.
3. Austrittsreihenfolge mit topologischer Sortierung verbinden.

Fallstricke

Nur den unmittelbaren Vorgänger auszuschliessen genügt in allgemeinen oder gerichteten Zyklen nicht. Grosse Graphen können ausserdem die sichere Rekursionstiefe überschreiten.