Tiefensuche

Tiefensuche

Die Tiefensuche (Depth First Search, DFS) ist die einfachste ihrer Art. Man hofft darauf, in einem der ersten durchsuchten Zweige auf die Lösung zu stoßen. Die Tiefensuche liefert meistens nicht den idealen Weg.

Vorgehensweise

Man hat einen Graphen, wovon man zuerst einen Ast bis zum letzten Element durchsucht und erst danach andere Äste in Betracht zieht. Wenn dieser Graph Zyklen aufweist, so kann dies sehr leicht zu einer endlosen Suche ausarten. Aus diesem Grund werden bereits besuchte Knoten meist also solche markiert. Beispiele für Graphen mit Zyklen:

• Ein Pfad wo man zwischen 2 Orten hin und zurück gehen kann.
• Eine Schach-Partie in der man mit einer Figur immer hin und her ziehen kann (gleich wie der Gegner)

Wenn jedoch bereits besuchte Knotenpunkte aus dem Graphen entfernt werden, so läuft dieser Algorithmus mit einer Geschwindigkeit von O(n), wobei n die Anzahl der Knoten ist; und einem Speicherbedarf von O(m) wobei m der längste Ast ist.

Algorithmus

Suche_Weg( Knoten Ziel, Knoten Aktuell )
  Wenn Aktuell = Ziel
    Ziel gefunden

  Für K = jeder noch nicht besuchte Nachbarknoten von Aktuell
    Suche_Weg( Ziel, K )

Tiefensuche mit Kosten

Bei der Tiefensuche sind Kosten für einen Weg ohne Bedeutung, es geht ausschließlich um die Anzahl der Knoten.