Tiefensuche

Tiefensuche (englisch: depth-first search, DFS) ist ein Fachbegriff der Informatik, welcher ein Verfahren zum Durchsuchen bzw. Durchlaufen der Knoten und Blätter einer baumartigen Datenstruktur (siehe auch Wälder und Bäume in der Graphentheorie) bezeichnet. Tiefensuche steht im Gegensatz zur Breitensuche (englisch: breadth-first search, BFS), wobei letztere im Allgemeinen speicheraufwändiger ist. Dafür terminiert die Tiefensuche nicht, falls mindestens ein Pfad des Baumes unendliche Länge hat.

Man startet an der Wurzel und geht so weit wie möglich entlang der bestehenden Kanten in die Tiefe, ehe man zurückgeht (englisch: backtracking) und dann in bislang unbesuchte Teilbäumen absteigt.

Formell betrachtet ist Tiefensuche eine uninformierte Suche, die voranschreitet durch expandieren des ersten auftretenden Kind-Knotens des Suchbaumes und so tiefer und tiefer geht bis sie einen Zielzustand gefunden hat oder einen Knoten, der keine Kinder hat. Dann geht die Suche zurück um von einem höher gelegenen Knoten wieder abzusteigen.

Algorithmisch betrachtet werden alle gerade expandierten Knoten in einen Stack zur weiteren Expansion gestellt.

• Tiefensuche ist vollständig: wenn der Baum endlich ist, wird eine Lösung gefunden, falls sie existiert
• Tiefensuche ist optimal, falls der Baum endlich ist und alle Pfadkosten nicht-negativ sind

Siehe auch: Iterative Tiefensuche