Tiefensuche

Suchalgorithmus in der Informatik (Graphentheorie)

Tiefensuche (englisch depth-first search, DFS) ist in der Informatik ein Verfahren zum Suchen von Knoten in einem Graphen. Sie zählt zu den uninformierten Suchalgorithmen. Im Gegensatz zur Breitensuche wird bei der Tiefensuche zunächst ein Pfad vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden[1]. Dabei sollen alle erreichbaren Knoten des Graphen besucht werden. Für Graphen mit potentiell wenigen, langen Pfaden bietet sich die beschränkte Tiefensuche an, bei der jeder Pfad nur bis zu einer bestimmten Tiefe beschritten wird.

Animation der Tiefensuche in einem Baum

Eine Verbesserung der Tiefensuche ist die iterative Tiefensuche.

AllgemeinesBearbeiten

Die Tiefensuche ist ein uninformierter Suchalgorithmus, welche durch Expansion des jeweils ersten auftretenden Nachfolgeknotens im Graphen nach und nach vom Startknoten aus weiter in die Tiefe sucht. In welcher Reihenfolge die Nachfolger eines Knotens dabei bestimmt werden, hängt von der Repräsentation der Nachfolger ab. Bei der Repräsentation über eine Adjazenzliste mittels einer verketteten Liste werden beispielsweise die Knoten in der Reihenfolge ihres Eintrags in dieser Liste durchlaufen. Im oben angegebenen Bild wird implizit davon ausgegangen, dass die Nachfolger von links nach rechts ausgewählt werden.

Für ungerichtete Graphen sieht das Verfahren wie folgt aus: Zuerst wird ein Startknoten   ausgewählt. Von diesem Knoten aus wird nun die erste Kante   betrachtet und getestet, ob der gegenüberliegende Knoten   schon entdeckt wurde bzw. das gesuchte Element ist. Ist dies noch nicht der Fall, so wird rekursiv für diesen Knoten die Tiefensuche aufgerufen, wodurch wieder der erste Nachfolger dieses Knotens expandiert wird. Diese Art der Suche wird solange fortgesetzt, bis das gesuchte Element entweder gefunden wurde oder die Suche bei einer Senke im Graphen 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 der Tiefensuche auf einen Baum zeigt die Animation.

Die Kanten des Graphen, die vom Algorithmus zum Durchlaufen des Graphen benutzt werden, werden als Baumkanten bezeichnet. Diejenigen Kanten, die nicht benutzt werden und von einem Knoten zu einem anderen Knoten im selben Teilbaum führen, der bei der Tiefensuche später besucht wird, heißen Vorwärtskanten. Diejenigen Kanten, die nicht benutzt werden und von einem Knoten zu einem anderen Knoten im selben Teilbaum führen, der bei der Tiefensuche bereits vorher besucht wurde, heißen Rückwärtskanten. Diejenigen Kanten, die „quer“ von einem Teilbaum zu einem anderen Teilbaum verlaufen, heißen Querkanten. Innerhalb des Tiefensuchbaums würde der Pfad zwischen zwei über eine Querkante verbundenen Knoten zunächst ein Auf- und dann ein Absteigen im Baum erfordern. Vorwärtskanten, Rückwärtskanten, Querkanten und Baumkanten ergeben insgesamt die Kantenmenge des Graphen.

AlgorithmenBearbeiten

  1. Bestimme den Knoten, an dem die Suche beginnen soll
  2. Expandiere den Knoten und speichere der Reihenfolge nach den kleinsten/größten (optional) noch nicht erschlossenen Nachfolger in einem Stack
  3. Rufe rekursiv für jeden der Knoten in dem Stack DFS auf
    • Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere ein Ergebnis
    • Falls es keine nicht erschlossenen Nachfolger mehr gibt, lösche den obersten Knoten aus dem Stack und rufe für den jetzt oberen Knoten im Stack DFS auf
DFS(node, goal) {
  if (node == goal) {
    return node;
  } else {
    stack:= expand (node)
    while (stack is not empty) {
      node':= pop(stack);
      DFS(node', goal);
    }
  }
}

Erzeugen des TiefensuchwaldesBearbeiten

Der folgende rekursive Algorithmus erzeugt den Tiefensuchwald eines Graphen G mittels Setzen von Discovery- und Finishing-Times und Färben der Knoten. In Anlehnung an Cormen et al. werden zunächst alle Knoten weiß gefärbt. Anschließend startet die Tiefensuche per Definition beim alphabetisch kleinsten Knoten und färbt diesen grau. Danach wird, wie oben beschrieben rekursiv dessen weißer Nachbar betrachtet und grau gefärbt. Existiert kein weißer Nachbar mehr, kommt es zum Backtracking, während dessen alle durchwanderten Knoten schwarz gefärbt werden.[2]

DFS(G)
1   for each v of G {        // Alle Knoten weiß färben, Vorgänger auf nil setzen
2      col[v] = 'w';
3      pi[v] = nil;
4   }
5   time = 0;
6   for each u of G          // Für alle weißen Knoten: DFS-visit aufrufen
7      if col[u] == 'w'
8         DFS-visit(u);
DFS-visit(u)
1   col[u] = 'g';            // Aktuellen Knoten grau färben
2   time++;                  // Zeitzähler erhöhen
3   d[u] = time;             // Entdeckzeit des aktuellen Knotens setzen
4   for each v of Adj[u] {   // Für alle weißen Nachbarn des aktuellen Knotens
5       if col[v] == 'w' {
6          pi[v] = u;         // Vorgänger auf aktuellen Knoten setzen
7          DFS-visit(v);      // DFS-visit aufrufen
8       }
9       if col[v] == 'g'{
10         // Zyklus entdeckt
11      }
12    }
13   col[u] = 's';           // Aktuellen Knoten schwarz färben
14   time++;
15   f[u] = time;            // Finishing-Time des aktuellen Knotens setzen

Den Zeitstempel (siehe Zeilen 2, 14, 15) kann man weiterhin für eine topologische Sortierung verwenden. Nachdem ein Knoten schwarz gefärbt wurde, wird er einer Liste, absteigend nach den Werten f[u] für die Zeitstempel, hinzugefügt und man erhält eine topologische Reihenfolge. Wird ein Zyklus (siehe Zeile 9) entdeckt, ist dies nicht mehr möglich.

EigenschaftenBearbeiten

Im Folgenden werden Speicherbedarf und Laufzeit des Algorithmus in Landau-Notation angegeben. Wir gehen außerdem von einem gerichteten Graphen aus.

SpeicherplatzBearbeiten

Der Speicherbedarf des Algorithmus wird ohne den Speicherplatz für den Graphen, wie er übergeben wird, angegeben, denn dieser kann in verschiedenen Formen mit unterschiedlichem Speicherbedarf vorliegen, z. B. als verkettete Liste, als Adjazenzmatrix oder als Inzidenzmatrix.

Für die oben beschriebene Prozedur DFS(G) werden zunächst alle Knoten weiß gefärbt und die Referenzen für deren Vorgänger entfernt. Diese Informationen benötigt also für jeden Knoten konstanten Speicherplatz, also  . Insgesamt ergibt sich ein linearer Speicherbedarf von  , abhängig von der Anzahl der Knoten   (englisch vertices). Der Speicherbedarf der Variable time ist mit konstantem   gegenüber   vernachlässigbar. Anschließend wird für jeden Knoten u die Prozedur DFS-visit(u) aufgerufen. Da es sich hierbei nur um Kontrollstrukturen handelt, tragen sie nicht zum Speicherbedarf bei.

Die Prozedur DFS-visit(u) arbeitet auf der bereits aufgebauten Speicherstruktur in der alle Knoten abgelegt sind und erweitert diese pro Knoten noch um die Entdeckzeit und die Finishing-Time, jeweils konstant  . Das ändert nichts am bisherigen linearen Speicherbedarf  . Da sonst in DFS-visit(u) keine weiteren Variablen mehr eingeführt werden, hat die Tiefensuche einen Speicherbedarf von  .

LaufzeitBearbeiten

Falls der Graph als Adjazenzliste gespeichert wurde, müssen im Worst Case alle möglichen Pfade zu allen möglichen Knoten betrachtet werden. Damit beträgt die Laufzeit von Tiefensuche  , wobei   für die Anzahl der Knoten und   für die Anzahl der Kanten im Graph stehen.[3]

VollständigkeitBearbeiten

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

OptimalitätBearbeiten

Tiefensuche ist insbesondere bei monoton steigenden Pfadkosten nicht optimal, da eventuell ein Ergebnis gefunden wird, zu welchem ein sehr viel längerer Pfad führt als zu einem alternativen Ergebnis. Dafür wird ein solches Ergebnis im Allgemeinen deutlich schneller gefunden als bei der in diesem Fall optimalen, aber sehr viel speicheraufwendigeren Breitensuche. Als Kombination von Tiefen- und Breitensuche gibt es die iterative Tiefensuche.

AnwendungenBearbeiten

Algorithmus, der Tiefensuche verwendet, um einen Irrgarten zu erzeugen.

Die Tiefensuche ist indirekt an vielen komplexeren Algorithmen für Graphen beteiligt. Beispiele:

  • Das Lösen von Rätseln mit nur einer Lösung, z. B. Irrgärten. Die Tiefensuche kann angepasst werden, um alle Lösungen für einen Irrgarten zu finden, indem nur Knoten auf dem aktuellen Pfad in die besuchte Menge aufgenommen werden.
  • Für das Erzeugen eines Irrgartens kann eine zufällige Tiefensuche verwenden.

LiteraturBearbeiten

WeblinksBearbeiten

Commons: Tiefensuche – Sammlung von Bildern, Videos und Audiodateien
Wikibooks: Tiefensuche – Implementierungen in der Algorithmensammlung

EinzelnachweiseBearbeiten

  1. Volker Turau: Algorithmische Graphentheorie. 3. Auflage. Oldenbourg Wissenschaftsverlag, München 2009, ISBN 978-3-486-59057-9, S. 94–98.
  2. Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 3. Auflage. Oldenbourg Wissenschaftsverlag, München 2010, ISBN 978-3-486-59002-9, S. 613–622.
  3. Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2012, ISBN 978-3-8274-2803-5, S. 589–668.
  4. John Hopcroft, Robert E. Tarjan: Efficient planarity testing. In: Journal of the Association for Computing Machinery. 21, Nr. 4, 1974, S. 549–568. doi:10.1145/321850.321852.
  5. H. de Fraysseix, P. Ossona de Mendez, P. Rosenstiehl: Trémaux Trees and Planarity. In: International Journal of Foundations of Computer Science. 17, Nr. 5, 2006, S. 1017–1030. arxiv:math/0610935. doi:10.1142/S0129054106004248.
  6. a b Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 3. Auflage. Springer Vieweg, Wiesbaden 2012, ISBN 978-3-8348-1849-2, S. 152–157.