Kleines Nachschlagewerk Informatik
Tiefensuche
Worum geht es?
Möchte man einen Graphen durchlaufen, also alle Knoten besuchen, kann man dies mit der Tiefensuche bewerkstelligen.
Wie funktioniert die Tiefensuche?
Die Tiefensuche kann man mit einem einzelnen Forscher vergleichen, der ein Labyrinth erkunden möchte. Er geht so lange links, bis er an ein Ende oder eine bekannte Kreuzung kommt.

Analog tastet man sich vom Anfangsknoten vorwärts. Links bedeutet hier, dass man den ersten noch nicht besuchten Knoten nimmt, zu dem eine Verbindung existiert. Gibt es vom aktuellen Knoten keine weiteren Verbindungen zu unbesuchten Knoten, so geht man zurück, bis man wieder einen weiteren möglichen Weg gefunden hat. Sind alle Knoten besucht worden, endet das Verfahren.

Dies setzt voraus, dass man sich für jeden Knoten merkt, von welchem Knoten man gekommen ist und ob dieser schon besucht wurde.
Beispiel
Folgendes Beispiel soll die Tiefensuche verdeutlichen. Dabei werden die Knoten in alphabetischer Reihenfolge bearbeitet.



Die Reihenfolge ist somit A-B-D-E-F-G-C-H
Der Algorithmus

      Funktion Schritt(knoten)
          Markieren knoten als besucht
          Gib Knoten aus
          solange unbesuchte verbundene Knoten existieren
              knoten = erster unbesuchter Knoten
              Schritt(knoten)
    
      Markiere alle Knoten unbesucht
      knoten = Startknoten
      Schritt(knoten)