Tiefensuche

”Das eben geschieht den Menschen, die in einem Irrgarten hastig werden: Eben die Eile führt immer tiefer in die Irre.“
- Lucius Annaeus Seneca (4 n.Chr. – 65 n.Chr.)

Tiefensuche engl: Depth-First Search   DFS

Prinzip
Tiefensuche versucht durch stetiges Erweitern eines Weges zum Ziel zu gelangen. Führt dies nicht zum Ziel, werden durch Backtracking andere Verzweigungen gewählt.

Algorithmus

Es wird immer eine Kante vom zuletzt entdeckten Knoten v erforscht.
Gibt es keine solche Kante mehr, wird zum Knoten, von dem aus v entdeckt wurde, zurückgegangen (backtracking).
Die Suche wird so lange fortgesetzt, wie noch nicht besuchte Knoten existieren.
Sind alle von einem Knoten aus erreichbaren Knoten entdeckt und existieren noch unentdeckte Knoten,
so beginnt Tiefensuche mit einem noch nicht entdeckten Knoten.

Anwendung

- Man möchte die Zusammenhangskomponente zu einem gegebenen Punkt bestimmen,
  es werden also alle Knoten markiert, die von dem Ursprungsknoten aus erreichbar sind.
- Suche auf Bäumen, um möglichst schnell ein erlaubtes Blatt zu finden.
- Klassisches Beispiel: Ariadnes Klugheit - also Suche im Labyrinth - euch bereits vom Backtracking her bekannt ;-)

Aufgabe a) Schauen Sie sich zur Wirkungsweise der Tiefensuche diese Applets an: 1. und 2. sowie 3.