Informatik

Wie funktioniert Tiefensuche?

Die Tiefensuche (DFS, von engl. Depth-First Search) ist ein Algorithmus zur Durchquerung oder Suche in Graphen. Sie startet an einem Knoten, erkundet so weit wie möglich entlang eines Pfades und kehrt zurück, um unerforschte Pfade zu besuchen.

Algorithmus

• Wähle einen Startknoten.
• Markiere den aktuellen Knoten als besucht.
• Gehe zu einem benachbarten, unbesuchten Knoten und wiederhole den Prozess.
• Kehrt zurück, wenn keine unbesuchten Nachbarn mehr vorhanden sind.

Pseudocode

DFS(knoten):
    markiere knoten als besucht
    für jeden Nachbar in knoten:
        wenn Nachbar nicht besucht:
            DFS(Nachbar)

Beispiel

Für den Graphen:

Die Tiefensuche, beginnend bei Knoten $A$, könnte der Reihenfolge nach Knoten $A, B, D, F, C, E$ besuchen.