Tiefensuche

Grundidee

Tiefensuche, englisch depth-first search (DFS), ist ein Verfahren der Informatik zum Suchen und Besuchen von Knoten in einem Graphen. Ein Graph besteht aus Knoten und Kanten; Kanten verbinden Knoten miteinander. Die Tiefensuche gehört zu den uninformierten Suchalgorithmen, weil sie keine Zusatzinformation darüber nutzt, welcher Weg wahrscheinlich zum Ziel führt.

Der zentrale Unterschied zur Breitensuche ist die Suchrichtung: Die Tiefensuche verfolgt zuerst einen Pfad möglichst weit in die Tiefe, bevor sie zu Abzweigungen zurückkehrt und andere Pfade ausprobiert. Ziel ist, alle erreichbaren Knoten eines Graphen zu besuchen oder ein gesuchtes Element zu finden. Für Graphen mit wenigen, aber sehr langen Pfaden kann eine beschränkte Tiefensuche verwendet werden, bei der jeder Pfad nur bis zu einer bestimmten Tiefe verfolgt wird. Eine Verbesserung ist die iterative Tiefensuche, die Tiefen- und Breitensuche kombiniert.

Ablauf der Suche

Die Tiefensuche beginnt an einem Startknoten. Von dort wird jeweils der erste auftretende Nachfolger ausgewählt und weiterverfolgt. Welche Nachfolger zuerst kommen, hängt von der Darstellung des Graphen ab. Bei einer Adjazenzliste, also einer Liste der Nachbarknoten eines Knotens, werden die Knoten zum Beispiel in der Reihenfolge ihrer Einträge durchlaufen.

Für einen ungerichteten Graphen läuft das Verfahren so ab: Zuerst wird ein Startknoten u gewählt. Dann wird eine Kante (u, v) betrachtet und geprüft, ob der gegenüberliegende Knoten v schon entdeckt wurde oder das gesuchte Element ist. Wurde v noch nicht entdeckt, ruft der Algorithmus die Tiefensuche rekursiv für v auf. Rekursion bedeutet, dass sich eine Methode oder Prozedur selbst wieder aufruft. So wird wieder der erste Nachfolger des neuen Knotens untersucht.

Die Suche geht weiter, bis entweder das gesuchte Element gefunden wird oder der Algorithmus an einer Senke ankommt, also an einem Punkt, von dem aus keine neuen Nachfolger mehr untersucht werden können. Dann kehrt er zum zuletzt expandierten Knoten zurück. Dieses Zurückgehen heißt Backtracking. Dort prüft er den nächsten Nachfolger. Gibt es keinen weiteren Nachfolger, geht er Schritt für Schritt zum jeweiligen Vorgänger zurück.

Die Kanten, die der Algorithmus tatsächlich zum Durchlaufen nutzt, heißen Baumkanten. Nicht benutzte Kanten können weiter eingeteilt werden: Vorwärtskanten führen zu einem Knoten im selben Teilbaum, der später besucht wird; Rückwärtskanten führen zu einem Knoten im selben Teilbaum, der bereits vorher besucht wurde; Querkanten führen von einem Teilbaum zu einem anderen Teilbaum. Zusammen ergeben Baumkanten, Vorwärtskanten, Rückwärtskanten und Querkanten die Kantenmenge des Graphen.

Tiefensuchbaum und Beispiel

Der Baum, den die Tiefensuche durchläuft, ist ein Spannbaum des Graphen. Ein Spannbaum verbindet alle erreichten Knoten ohne unnötige Kanten. Dieser Baum hängt vom gewählten Startknoten ab. Außerdem ist wichtig, ob der Graph gerichtet oder ungerichtet ist.

Die Rekursionstiefe entspricht im dargestellten Baum dem Knotenabstand des gerade betrachteten Knotens vom Startknoten. Diese Tiefe müsste zum Beispiel in einer Variablen gespeichert werden, wenn sie auf der Konsole ausgegeben werden soll. Die rekursive Methode oder Prozedur wird so oft aufgerufen, wie es Knoten im Graphen gibt. Sie bricht ab, wenn der aktuelle Knoten nur Nachbarknoten hat, die schon vorher durchlaufen wurden.

Im Städtebeispiel wird Tiefensuche auf einen ungerichteten Graphen mit 10 Knoten angewendet und in Hannover gestartet. Der entstehende Baum hat die Höhe 6; daher beträgt die maximale Rekursionstiefe in diesem Fall 6. Die rekursiven Aufrufe lauten: Hannover mit Rekursionstiefe 0, Frankfurt 1, Zürich 2, München 3, Stuttgart 4, Hamburg 5, Mannheim 6, Dresden 5, Wien 4 und Berlin 5.

Der Knotenabstand bezieht sich immer auf den Startknoten. Bei gerichteten Graphen ist der Knotenabstand zwischen zwei verschiedenen Knoten nicht unbedingt symmetrisch. Für nicht zusammenhängende Graphen sind Knotenabstand und Rekursionstiefe nur innerhalb jeder Zusammenhangskomponente definiert. Die Reihenfolge der durchlaufenen Knoten kann sich ändern, wenn ein anderer Startknoten gewählt wird oder wenn ein gerichteter, nicht symmetrischer Graph verwendet wird.

Algorithmische Umsetzung

Ein einfacher Ablauf der Tiefensuche ist: Zuerst wird der Startknoten bestimmt. Dann wird der Knoten expandiert, das heißt seine Nachfolger werden betrachtet. Noch nicht erschlossene Nachfolger können in einem Stack gespeichert werden. Ein Stack ist eine Stapelstruktur, bei der zuletzt eingefügte Elemente zuerst wieder entnommen werden. Für jeden Knoten im Stack wird rekursiv DFS aufgerufen. Wird das gesuchte Element gefunden, bricht die Suche ab und liefert ein Ergebnis. Gibt es keine nicht erschlossenen Nachfolger mehr, wird der oberste Knoten aus dem Stack entfernt, und die Suche geht mit dem nun obersten Knoten weiter.

Ein rekursiver Algorithmus zur Erzeugung eines Tiefensuchwaldes färbt zunächst alle Knoten weiß und setzt ihre Vorgänger auf nil. Dann startet die Tiefensuche per Definition beim alphabetisch kleinsten Knoten und färbt ihn grau. Weiße Nachbarn werden rekursiv besucht und ebenfalls grau gefärbt. Wenn kein weißer Nachbar mehr existiert, beginnt Backtracking; dabei werden die durchlaufenen Knoten schwarz gefärbt.

Dabei werden Discovery-Times und Finishing-Times gespeichert. Die Discovery-Time d[u] ist der Zeitpunkt, zu dem ein Knoten u entdeckt wird. Die Finishing-Time f[u] ist der Zeitpunkt, zu dem die Bearbeitung von u abgeschlossen ist. Der Zeitstempel kann für eine topologische Sortierung verwendet werden: Nachdem ein Knoten schwarz gefärbt wurde, wird er einer Liste hinzugefügt, absteigend nach den Werten f[u]. So erhält man eine topologische Reihenfolge. Wird ein Zyklus entdeckt, ist dies nicht mehr möglich.

Programmierung und Eigenschaften

Die Tiefensuche lässt sich direkt rekursiv programmieren. Im C#-Beispiel des Artikels wird ein gerichteter Graph als Klasse DirectedGraph dargestellt. Jeder Knoten besitzt einen Index, einen Wert und eine Liste von Nachbarknoten. Die Methode DepthFirstSearch fügt den aktuellen Startknoten einer Liste der durchlaufenen Knoten hinzu. Danach geht sie alle Nachbarknoten durch und ruft sich für noch nicht markierte Knoten rekursiv auf. Im Beispiel werden die Knoten A, B, C und D verwendet; die Suche startet bei node3, also bei C.

Für die Nachbarknoten wird eine Liste verwendet, damit die Reihenfolge der durchlaufenen Knoten eindeutig ist und die Knoten in allen Ebenen von links nach rechts durchlaufen werden. Bei einer Menge wäre diese Reihenfolge nicht unbedingt festgelegt. Statt einer Liste der besuchten Knoten kann auch ein Array vom Typ bool verwendet werden.

Der Speicherbedarf wird ohne den Speicherplatz für den Graphen angegeben, weil der Graph unterschiedlich gespeichert sein kann, zum Beispiel als verkettete Liste, Adjazenzmatrix oder Inzidenzmatrix. Für jeden Knoten werden Informationen wie Farbe, Vorgänger, Entdeckzeit und Finishing-Time gespeichert. Pro Knoten ist das konstant, insgesamt ergibt sich daher ein linearer Speicherbedarf von O(|V|), wobei |V| die Anzahl der Knoten ist. Die Variable time benötigt nur O(1) Speicher.

Wenn der Graph als Adjazenzliste gespeichert ist, beträgt die Laufzeit im Worst Case O(|V| + |E|). Dabei steht |E| für die Anzahl der Kanten. Die Tiefensuche ist nicht vollständig, wenn ein Graph unendlich groß ist oder kein Test auf Zyklen durchgeführt wird: Dann kann ein vorhandenes Ergebnis unter Umständen nicht gefunden werden. Sie ist insbesondere bei monoton steigenden Pfadkosten nicht optimal, weil sie möglicherweise ein Ergebnis über einen viel längeren Pfad findet als ein alternatives Ergebnis. Dafür kann sie ein Ergebnis im Allgemeinen schneller finden als die in diesem Fall optimale, aber speicheraufwendigere Breitensuche.

Anwendungen

Tiefensuche wird indirekt in vielen komplexeren Graphalgorithmen verwendet. Dazu gehören das Auffinden aller starken Zusammenhangskomponenten eines Graphen, das Ermitteln von 2-zusammenhängenden und 3-zusammenhängenden Komponenten sowie das Ermitteln der Brücken eines Graphen.

Mit Tiefensuche kann man prüfen, ob ein Graph planar ist. Bei einem Baum, der Abhängigkeiten darstellt, ergeben die sortierten finish-Zeiten eine invers-topologische Sortierung. Außerdem kann man Graphen in Laufzeit O(|V| + |E|) auf Kreise testen und im Fall von Kreisen die zugehörige Kantenfolge ausgeben. Ein kreisfreier Graph kann mit Tiefensuche ebenfalls in Laufzeit O(|V| + |E|) topologisch sortiert werden.

Ein typisches Beispiel ist das Lösen von Rätseln mit nur einer Lösung, etwa Irrgärten. Die Tiefensuche kann angepasst werden, um alle Lösungen eines Irrgartens zu finden: Dann werden nur Knoten auf dem aktuellen Pfad in die besuchte Menge aufgenommen. Auch zum Erzeugen eines Irrgartens kann eine zufällige Tiefensuche verwendet werden.