Tiefensuche

Tiefensuche (englisch: depth-first search, DFS) ist in der Informatik ein Verfahren zum Suchen eines Knotens in einem Graphen. Eine Verbessung der Tiefensuche ist die Iterative Tiefensuche.

Tiefensuche

Reihenfolge im Beispielbaum

Allgemeine Daten

Klasse:	Suchalgorithmus
Datenstruktur:	Graph
Zeitkomplexität:	$O(\|V\|+\|E\|)$
Platzkomplexität:
Optimal:	nein
Vollständig:	nein

Allgemeines

Die Tiefensuche ist eine Uninformierte Suche, welche durch Expansion des jeweils ersten auftretenden Nachfolgeknotens im Graph nach und nach vom Startknoten aus weiter in die Tiefe sucht. Diese Art der Suche wird solange fortgesetzt, bis das gesuchte Element entweder gefunden wurde oder die Suche bei einer Senke im Graph angekommen ist und somit keine weiteren Nachfolgeknoten mehr untersuchen kann. An dieser Stelle kehrt der Algorithmus nun zum zuletzt expandierten Knoten zurück und untersucht den nächsten Nachfolger des Knotens. Sollte es hier keine weiteren Nachfolger mehr geben, geht der Algorithmus wieder Schritt für Schritt zum jeweiligen Vorgänger zurück und versucht es dort erneut. Ein Beispiel für die Anwendung von Tiefensuche auf einem Baum findet man im oben stehenden Bild.

Algorithmus (informal)

Bestimme den Knoten an dem die Suche beginnen soll
Expandiere den Knoten und speichere alle Nachfolger in einem Stack
Rufe rekursiv für jeden der Knoten in dem Stack DFS auf
- Falls der Stack leer sein sollte, tue nichts
- Falls das gesuchte Element gefunden worden sein sollte, brich die Suche ab und liefere ein Ergebnis

Algorithmus (formal)

DFS(node, goal)
{
  if (node == goal)
    return node;
  else
  {
    stack := expand (node)
    while (stack is not empty)
    {
      node' := pop(stack);
      DFS(node', goal);
    }
  }
}

Eigenschaften

Laufzeit

Da im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen, beträgt die Laufzeit von Tiefensuche O( $\vert V\vert +\vert E\vert$ ) wobei $\vert V\vert$ für die Anzahl der Knoten und $\vert E\vert$ für die Anzahl der Kanten im Graph steht.

Vollständigkeit

Falls ein Graph unendlich groß ist oder kein Test auf Zyklen durchgeführt wird, so ist Tiefensuche nicht vollständig. Es kann also sein, dass ein Ergebnis - obwohl es existiert - nicht gefunden wird.

Optimalität

Tiefensuche ist nicht optimal, da eventuell ein Ergebnis gefunden wird, zu welchem ein sehr viel längerer Pfad führt als zu einem alternativen Ergebnis.

Siehe auch

Literatur

Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2nd edition 2001, ISBN 0262531968
Stuart Russell, Peter Norvig: Artificial Intelligence: A Modern Approach, 2. Auflage, 2002, Prentice Hall.