Tiefensuche (DFS): Ablauf, Stack und Beispiele

Ein Graph besteht aus Knoten (Punkten) und Kanten (Verbindungen zwischen Knoten). Die Tiefensuche (englisch depth-first search, kurz DFS) durchsucht einen Graphen so: Sie startet bei einem Startknoten und geht zuerst einen Pfad ganz in die Tiefe, bevor sie zu abzweigenden Pfaden kommt.

So gehst du vor: Erstens gehst du vom aktuellen Knoten zum ersten Nachbarn, der noch nicht entdeckt ist. Zweitens rufst du dort dieselbe Suche noch einmal auf (rekursiv). Drittens: Hat ein Knoten keinen weiteren Nachfolger mehr, geht die Suche Schritt für Schritt zum Vorgänger zurück und versucht es dort mit dem nächsten Nachbarn.

Welcher Nachbar der „erste“ ist, hängt von der Darstellung des Graphen ab. Bei einer Adjazenzliste (für jeden Knoten eine Liste seiner Nachbarn) als verkettete Liste kommen die Nachbarn in der Reihenfolge ihres Eintrags in der Liste dran. Bei einer Aufgabe ist die Nachbarreihenfolge deshalb eine Vorgabe, die du genau einhalten musst.

Mit einem anderen Startknoten oder bei einem gerichteten Graphen (die Kanten haben eine Richtung), der nicht symmetrisch ist, kann sich die Reihenfolge der durchlaufenen Knoten ändern.

Die Besuchsmarkierung: In vielen Graphen gibt es Kreise (Zyklen). Dann kommt man über Kanten zu einem Knoten zurück, an dem man schon war. Wird kein Test auf Zyklen gemacht, ist die Tiefensuche nicht vollständig: Ein Ergebnis, das es gibt, kann dann unentdeckt bleiben. Deshalb wird ein Knoten beim Besuch als besucht markiert. In einer Java-Umsetzung geht die Suche nur zu Knoten weiter, die erreichbar und noch nicht besucht sind. Auch das Ende eines Aufrufs hängt daran: Er endet, wenn der Knoten nur Nachbarn hat, die schon vorher durchlaufen wurden.

Der Weg zurück: Wenn ein Knoten keine neuen Nachbarn mehr hat, muss die Suche zum Vorgänger zurück. Dafür muss sie sich merken, über welche Knoten sie gekommen ist. Ein Stack (deutsch Stapel) ist dafür geeignet: Elemente können nur oben aufgelegt (push) und nur von dort wieder genommen werden (pop). Sie kommen in umgekehrter Reihenfolge wieder heraus (englisch Last-In-First-Out).

Bei Rekursion übernimmt der Stack des Programms diese Aufgabe: Jede aufgerufene Prozedur legt ihre Rückgabeinformationen und lokalen Daten auf den Stack, beim Aufruf eines Unterprogramms auch die Rücksprungadresse. Das erlaubt Rekursion, also den Aufruf einer Funktion aus ihr selbst heraus.

Wandelt man ein rekursives Unterprogramm in ein iteratives um, muss dieser Mechanismus häufig ausdrücklich selbst umgesetzt werden. Eine iterative Tiefensuche speichert dann in einem Stack den bereits entdeckten Weg bis zu einem Knoten ohne neuen Nachbarn. Der Stack wird abgetragen, bis ein gespeicherter Knoten noch einen weiteren neuen Nachbarn hat oder der Stack leer ist. Damit wird das Zurückgehen der Rekursion nachgebildet.

Erreichbarkeit: Die Tiefensuche soll alle erreichbaren Knoten des Graphen besuchen. Auch die Breitensuche (englisch breadth-first search, kurz BFS) findet alle Knoten des Teils vom Graphen, in dem der Startknoten liegt (Fachwort: Zusammenhangskomponente). Im Beispiel bleiben F und G bei beiden Verfahren unerreicht, weil sie nur miteinander verbunden sind und nicht mit S.

Der Unterschied liegt im Vorgehen: Die Breitensuche besucht zuerst alle Knoten, die vom Startknoten direkt erreichbar sind, und erst danach die Folgeknoten. Dafür nimmt sie den ersten Knoten aus einer Warteschlange und hängt dessen noch nicht markierte Nachfolger hinten an. Die Tiefensuche folgt dagegen zuerst einem Pfad in die Tiefe.

Kürzeste Wege: Jede durch Breitensuche gefundene Lösung hat den kürzesten Abstand zum Wurzelknoten. Mit ihr findest du bei ungewichteten Kanten einen kürzesten Pfad zwischen zwei Knoten. Sind den Kanten Gewichte zugeordnet, muss das Ergebnis, das dem Start am nächsten liegt, nicht das mit den geringsten Pfadkosten sein. Die Tiefensuche ist bei monoton steigenden Pfadkosten (Kosten, die entlang eines Pfades nicht sinken) nicht optimal, weil eventuell ein Ergebnis gefunden wird, zu dem ein sehr viel längerer Pfad führt als zu einem anderen.

Die Laufzeit unterscheidet die beiden nicht: Bei beiden beträgt sie O(|V|+|E|). Dabei ist |V| die Zahl der Knoten und |E| die Zahl der Kanten. Die Tiefensuche ist also nicht schon deshalb schneller.