Tiefensuche

Die Tiefensuche (DFS) ist ein Algorithmus zur Durchsuchung oder Traversierung eines Baumes oder Graphen. Im Gegensatz zur Breitensuche geht DFS so tief wie möglich in eine Richtung, bevor es zurückgeht und andere Pfade erkundet.

Einführungsbeispiel

Beispiel anhand des gegebenen Baumes: Der Baum beginnt mit dem Startknoten S (1). Die DFS erkundet den Baum in folgender Reihenfolge:

Wichtig: Die genaue Reihenfolge hängt davon ab, in welcher Reihenfolge die Kinder eines Knotens besucht werden

Eigenschaften

Beispiel 1

Übungen 1

Zeichnen Sie den Graphen, der aus welchem der dargestellte Baum abgeleitet werden könnte. Was fällt Ihnen auf?

Der im Beispiel abgebildete Baum ist nicht vollständig, weil bereits einige Knoten gepruned wurden. Was passiert, wenn Sie im Graphen die Tiefensuche von S aus beginnen und als Regel immer den Knoten als nächstes öffnen, welcher im Alphabet zuerst kommt? Schalten Sie dazu beim Baum rechts Pruning aus.
Sie beginnen bei S und wählen dann als nächsten Knoten A, weil der Buchstabe vor den anderen Optionen (B und E) liegt. Wenn diesen Prozess weiterführen resultiert daraus folgender Pfad:
S → A → E → A → E → A → E...
Sie drehen sich also unendlich oft im Kreis.
Was passiert, wenn Sie im Graphen die Tiefensuche von S aus beginnen und als Regel immer den Knoten als nächstes öffnen, welcher im Alphabet an zweiter Stelle kommt? Schalten Sie dazu beim Baum rechts Pruning aus.
Sie beginnen bei S und wählen dann als nächsten Knoten B, weil der Buchstabe an zweiter Stelle im Alphabet liegt (nach A und vor E). Wenn diesen Prozess weiterführen resultiert daraus folgender Pfad:
S → B → D → G
Falls Sie mit der Tiefensuche eine Lösung zum Ziel finden, ist es jeweils zwingend die kürzeste Lösung zum Ziel?
Nein, wie das Beispiel oben gezeigt hat, finden sie zwar einen Weg zum Ziel, dieser ist jedoch nicht optimal. Es gäbe einen kürzeren Weg:
S → A → G
Wann kann die Tiefensuche ohne Bedenken angewendet werden? Wann nicht?
Die Tiefensuche kann dann ohne Bedenken angewendet werden, wenn der Graph azyklisch ist (Sie sich also nicht im Kreis drehen können). Diese Eigenschaft kann von einem Graph selbst bereits gegeben sein, falls nicht, erreichen Sie diese Eigenschaft, indem Sie Knoten im Suchbaum prunen, die Sie bereits besucht haben. Ansonsten ist nicht garantiert, dass die Tiefensuche terminiert (ein Ende findet). Es ist theoretisch aber möglich, dass Sie auch in einem zyklischen Graphen mit der Tiefensuche eine Lösung finden.