DFS Visualisierer Online

Pseudocode

DFS wird meist rekursiv geschrieben, doch die iterative Form macht den Stapel explizit und vermeidet einen Überlauf des Aufrufstapels bei tiefen Graphen. Beide erzeugen dieselbe Entdeckungsreihenfolge.

DFS(graph, quelle):
    zeit = 0
    besuche(quelle)

besuche(u):
    besucht.hinzufügen(u)
    entd[u] = ++zeit            // Entdeckungszeit
    für jeden Nachbarn v von u:
        wenn v nicht in besucht:
            vorgänger[v] = u
            besuche(v)
    fertig[u] = ++zeit          // Abschlusszeit

Die Entdeckungs- und Abschlusszeiten sind das eigentliche Ergebnis von DFS. Das Intervall [entd[u], fertig[u]] eines Nachfahren liegt strikt geschachtelt im Intervall seines Vorfahren, und diese Schachtelung ist die Grundlage von topologischer Sortierung, Zyklenerkennung, Tarjans starken Zusammenhangskomponenten, Artikulationspunkten und Brücken.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe DFS von A aus auf dem Graphen, den der Visualisierer standardmäßig lädt, und nimm die Nachbarn stets in alphabetischer Reihenfolge.

Beispielgraph: Ungerichtete Kanten A-B (2), A-C (3), B-C (1) und C-D (4). DFS ignoriert die Gewichte.

1. A besuchen. entd[A] = 1. Der erste unbesuchte Nachbar ist B, also folgt sofort die Rekursion, statt auch C anzusehen.
2. B besuchen. entd[B] = 2. Nachbarn sind A, der Vorgänger und wird übersprungen, sowie C, unbesucht. Rekursion in C.
3. C besuchen. entd[C] = 3. Nachbarn sind A, B und D. A ist besucht und nicht der Vorgänger, also ist A-C eine Rückkante und beweist einen Zyklus. B ist der Vorgänger. D ist unbesucht, also Rekursion in D.
4. D besuchen. entd[D] = 4. Einziger Nachbar ist C, der Vorgänger. Es bleibt nichts zu tun, also fertig[D] = 5.
5. Rekursion abwickeln. Die Kontrolle kehrt zu C zurück, dem die Nachbarn ausgehen, also fertig[C] = 6. Danach schließt B bei 7 ab, und A, dessen verbleibender Nachbar C nun besucht ist, bei 8.

Die Durchlaufreihenfolge ist A, B, C, D. BFS besucht dieselben vier Knoten in derselben Reihenfolge, doch die Bäume unterscheiden sich: BFS baut einen flachen Baum mit A zu B, A zu C und C zu D, DFS dagegen die einzelne Kette A zu B zu C zu D. Die Rückkante C zu A kennzeichnet den Zyklus A-B-C-A, und die geschachtelten Intervalle A[1,8], B[2,7], C[3,6], D[4,5] zeigen die Rekursionstiefe unmittelbar.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V)

Jeder Knoten wird genau einmal besucht, weil die Besuchtprüfung den rekursiven Aufruf absichert, und jede Kante wird von jedem Endpunkt einmal betrachtet, was 2E Prüfungen im ungerichteten und E im gerichteten Fall ergibt. Der Speicher besteht aus Besuchtmenge und Rekursionsstapel, beide O(V). Die Rekursionstiefe entspricht der Länge des längsten einfachen Weges, sodass eine rekursive Implementierung bei einem Pfadgraphen mit einer Million Knoten in den meisten Sprachen den Aufrufstapel überläuft und die Variante mit explizitem Stapel nötig wird.

Wann Tiefensuche passt und wann nicht

Wähle DFS, wenn die Frage auf Struktur zielt. Wähle BFS, wenn sie auf Distanz zielt.

Häufige Fehler

• Stapelüberlauf bei tiefen Graphen. Rekursive DFS ruft sich auf einem Pfad einmal je Knoten auf. Je nach Sprache stirbt der Aufrufstapel bei etwa 10.000 bis 100.000 Knoten. Wandle in einen expliziten Stapel um oder erhöhe die Rekursionsgrenze bewusst, sofern die Sprache das erlaubt.
• Die Kante zum Vorgänger als Rückkante behandeln. In einem ungerichteten Graphen erscheint jede Kante von beiden Seiten, sodass die Kante zurück zum Vorgänger stets wie eine Rückkante aussieht. Überspringe den Vorgänger ausdrücklich, und bedenke bei Mehrfachkanten, dass du ihn nur einmal überspringen darfst.
• Die Besuchtmenge zur Zyklenerkennung in gerichteten Graphen nutzen. In einem gerichteten Graphen bedeutet ein besuchter Knoten keinen Zyklus. Es kann eine Querkante in einen bereits abgeschlossenen Teilbaum sein. Du brauchst drei Farben: unbesucht, im aktuellen Rekursionsstapel, abgeschlossen. Nur eine Kante in den Rekursionsstapel schließt einen Zyklus.
• Annehmen, die Durchlaufreihenfolge sei eindeutig. Die Ausgabe von DFS hängt von der Reihenfolge der Nachbariteration ab. Zwei korrekte Implementierungen können verschiedene gültige Reihenfolgen liefern, weshalb Tests Eigenschaften prüfen sollten und keine exakte Sequenz.

Häufig gestellte Fragen

Wofür wird die Tiefensuche verwendet?

DFS trägt topologische Sortierung, Zyklenerkennung, starke Zusammenhangskomponenten, Artikulationspunkte und Brücken sowie Labyrintherzeugung. In der Praxis steckt sie hinter der Abhängigkeitsauflösung in Build-Werkzeugen und Paketmanagern, der Deadlock-Erkennung und Backtracking-Lösern.

Wie ist die Zeitkomplexität von DFS?

O(V + E) Zeit und O(V) Speicher mit Adjazenzliste. Jeder Knoten wird einmal besucht und jede Kante von jedem Endpunkt einmal geprüft. Der Speicher umfasst die Besuchtmenge und den Rekursionsstapel, dessen Tiefe dem längsten einfachen Weg im Graphen entspricht.

Ist DFS rekursiv oder iterativ?

Beides ist möglich. Die rekursive Form ist kürzer und liefert Entdeckungs- und Abschlusszeiten ganz natürlich. Die iterative nutzt einen expliziten Stapel und ist nötig bei Graphen, die tief genug sind, um den Aufrufstapel zu überlaufen, also bei Ketten von einigen zehntausend Knoten.

Wie erkennt DFS einen Zyklus?

In einem ungerichteten Graphen schließt eine Kante zu einem besuchten Knoten, der nicht der Vorgänger ist, einen Zyklus. In einem gerichteten Graphen musst du festhalten, welche Knoten im aktuellen Rekursionsstapel liegen, denn nur eine Kante zurück in den Stapel ist eine echte Rückkante. Eine Kante zu einem abgeschlossenen Knoten ist eine Quer- oder Vorwärtskante und beweist nichts.

Warum braucht DFS weniger Speicher als BFS?

DFS speichert nur den aktuellen Weg von der Wurzel zum Knoten, ihr Speicher ist also proportional zur Tiefe. BFS speichert eine ganze Front, die bei einem breiten Graphen einen großen Teil aller Knoten ausmachen kann. Bei einem tiefen, schmalen Graphen kehrt sich der Vergleich um und BFS ist die leichtere Wahl.