Definition - Tiefensuche

• Beispiele:
  • AlMa EA2.1
• Generalisierungen:
  • Suchverfahren
• Involvierte Definitionen:
  • Graph
• Veranstaltung:
  • AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Tiefensuche

Die Tiefensuche ist ein Verfahren zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen.

Ausgehend vom Startknoten wird der Graph in die Tiefe nach einem Element durchsucht.

1. Wähle einen Startknoten aus.
2. Speichere den ausgewählten Knoten als Besucht in einer mit dem Vorgänger-Knoten verketteten Liste ab.
3. Wähle den nächsten, noch nicht besuchten Knoten aus den Nachbarn des ausgewählten Knotens aus und fahre fort wie in 2.
4. Wurden bereits alle Nachbarknoten des ausgewählten Knotens besucht, gehe die verkettete Liste der besuchten Knoten so lange rückwärts, bis es wieder unbesuchte Nachbarn gibt.
5. Fahre fort wie in 3.
6. Kann in der verketteten Liste nicht mehr weiter zurückgegangen werden, stoppt der Algorithmus.

Anmerkung