Mit Google fortfahren
Tiefensuche (DFS): Ablauf, Stack und Beispiele
Die Tiefensuche (englisch Depth-First Search, kurz DFS) verfolgt in einem Graphen zuerst einen Weg so weit wie möglich. Trifft sie auf eine Sackgasse, kehrt sie zur letzten offenen Abzweigung zurück. Dieses Zurückgehen heißt Backtracking.
Du lernst hier, eine Tiefensuche von Hand auszuführen, sie mit Rekursion oder Stack zu erklären und zu entscheiden, wann ein anderes Verfahren besser passt.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Wie die Tiefensuche denkt
Ein Graph besteht aus Knoten und Kanten. Knoten stellen zum Beispiel Orte dar; Kanten zeigen, welche Orte direkt verbunden sind. In einem gerichteten Graphen darf eine Kante nur in Pfeilrichtung durchlaufen werden.
Tiefensuche
Die Tiefensuche ist ein Verfahren zum Durchlaufen eines Graphen. Sie besucht einen noch unbekannten Nachbarn, setzt die Suche von dort fort und geht erst bei einer Sackgasse zurück.
Stell dir ein Labyrinth vor: Du folgst einem Gang bis zum Ende. Dann gehst du zur letzten Abzweigung zurück und probierst den nächsten noch nicht untersuchten Gang.
Welche Route DFS konkret nimmt, hängt vom Startknoten und von der Reihenfolge der Nachbarn ab. Darum muss diese Reihenfolge feststehen, wenn du eine Besuchsfolge eindeutig angeben willst.
Erst tief, dann zurück: DFS verfolgt die zuletzt gewählte Fortsetzung zuerst.
So führst du DFS Schritt für Schritt aus
Betrachte diesen gerichteten Graphen. Die Nachbarn stehen bereits in der Reihenfolge, in der DFS sie prüft:
text A: B, C B: D, E C: E D: — E: A
Starte bei A und führe die rekursive DFS aus:
- Besuche
Aund markiereA. - Gehe zum ersten unbesuchten Nachbarn
B. - Von
Bgehst du zuerst zuD. Dort gibt es keine Fortsetzung: zurück zuB. - Der nächste unbesuchte Nachbar von
BistE. Die Kante vonEzuAführt zu einem bereits besuchten Knoten, also folgt kein neuer Aufruf. - Zurück bei
AbleibtC. Dessen NachbarEist bereits besucht.
Die Besuchsreihenfolge lautet damit:
text A, B, D, E, C
Der entscheidende Schritt ist das Backtracking nach D: DFS springt nicht sofort zu C, sondern kehrt zu B zurück, weil dort mit E noch eine offene Abzweigung liegt.
Ein passender rekursiver Ablauf sieht so aus:
text DFS(u): markiere u als besucht für jeden Nachbarn v von u in festgelegter Reihenfolge: wenn v noch nicht besucht ist: DFS(v)
Die Markierung geschieht vor den rekursiven Aufrufen. Sonst könnten Kanten wie E → A eine endlose Aufrufkette erzeugen.
Rekursion und Stack setzen dieselbe Strategie um
Bei der Rekursion ruft die Funktion sich für einen Nachbarn selbst auf. Die noch nicht beendeten Funktionsaufrufe merken sich automatisch, zu welcher Abzweigung die Suche zurückkehren muss.
Die gleiche Strategie lässt sich ohne rekursive Aufrufe mit einem Stack umsetzen. Ein Stack arbeitet nach dem LIFO-Prinzip: Das zuletzt abgelegte Element wird zuerst entnommen.
```text markiere start als besucht lege start auf den Stack
solange der Stack nicht leer ist: nimm den obersten Knoten u herunter verarbeite u lege unbesuchte Nachbarn auf den Stack markiere sie dabei als besucht ```
Werden Nachbarn schon beim Ablegen markiert, wird derselbe Knoten nicht mehrfach als offen eingeplant. Soll die oben notierte Nachbarreihenfolge gelten, müssen die Nachbarn beim iterativen Verfahren häufig in umgekehrter Reihenfolge auf den Stack gelegt werden: Der zuletzt abgelegte liegt oben und wird als Nächstes entnommen.
Iterative DFS mit einem Stack und iterative Tiefenvertiefung sind nicht dasselbe. Bei der Tiefenvertiefung wird DFS mehrfach mit einer schrittweise erhöhten Tiefengrenze ausgeführt.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Die rekursive DFS nutzt den . Die iterative DFS nutzt einen expliziten . Wegen des wird das zuletzt abgelegte Element zuerst entnommen. Eine frühe verhindert, dass derselbe Knoten mehrfach als offen eingeplant wird.
Erreichbarkeit und gefundene Pfade
DFS eignet sich gut für die Frage: Gibt es vom Start einen Pfad zum Ziel? Sobald das Ziel entdeckt ist, kann die Suche beendet werden.
Möchtest du den gefundenen Pfad ausgeben, speicherst du für jeden neu entdeckten Knoten seinen Vorgänger. Im Beispiel wird E von B aus entdeckt. Deshalb gilt:
text Vorgänger von E = B Vorgänger von B = A
Vom Ziel rückwärts gelesen entsteht E ← B ← A. Umgedreht lautet der gefundene Pfad:
text A → B → E
DFS findet hier einen Pfad von A nach E. Sie beweist damit die Erreichbarkeit. Sie beweist aber nicht, dass dieser Pfad unter allen möglichen Pfaden der kürzeste ist.
Auch Flood Fill nutzt dieselbe Idee: Ein Rasterfeld ist ein Knoten, orthogonal benachbarte Felder gleicher alter Farbe sind verbunden. Nach dem Umfärben eines Feldes werden seine vier Nachbarn untersucht. Randprüfungen und die Prüfung der alten Farbe bilden die Abbruchbedingungen.
Wann DFS passt – und wann nicht
DFS und Breitensuche (BFS) besuchen erreichbare Knoten, ordnen die offenen Knoten aber verschieden:
| Frage | Tiefensuche (DFS) | Breitensuche (BFS) |
|---|---|---|
| Welche Fortsetzung kommt zuerst? | der zuletzt begonnene, tiefe Zweig | zunächst alle Knoten derselben Ebene |
| Typische Datenstruktur | Stack oder Rekursion | Warteschlange |
| Kürzester Pfad im ungewichteten Graphen | nicht garantiert | nach Kantenzahl garantiert |
| Typische Stärke | Erreichbarkeit, vollständiges Durchlaufen, tiefe Suche | nahe Ziele, kürzeste Wege nach Kantenzahl |
Bei einer Adjazenzliste kann eine vollständige DFS jeden Knoten und jede Kante systematisch durchlaufen. Die Laufzeit liegt dann in O(|V| + |E|): |V| bezeichnet die Anzahl der Knoten, |E| die Anzahl der Kanten. Eine Adjazenzmatrix prüft dagegen für jeden besuchten Knoten eine ganze Zeile; bei |V| Knoten liegt der Aufwand typischerweise in O(|V|²).
Die Besuchsmarkierung sowie der Rekursionszustand oder der explizite Stack können zusammen zusätzlichen Speicher in O(|V|) benötigen.
Für einen endlichen Graphen verhindert die Besuchsmarkierung, dass DFS in einem Zyklus endlos weiterläuft. In einem gerichteten Graphen kann eine Kante zu einem gerade aktiven, noch nicht abgeschlossenen Knoten auf einen Zyklus hinweisen. Eine Kante zu irgendeinem früher besuchten Knoten genügt für diese Aussage nicht immer.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Tiefensuche
- Strategie: erst tief, dann Backtracking
- Zustand: besucht oder noch unbesucht
- Umsetzung: Rekursion oder Stack
- Ergebnis: Erreichbarkeit und gefundener Pfad
- Reihenfolge: abhängig von Start und Nachbarordnung
- Grenze: kein garantiert kürzester Pfad
- Aufwand mit Adjazenzliste: O(|V| + |E|)