Tiefensuche

#Studium #Informatik #Definition #DS

Die Tiefensuche (DFS) ist ein Verfahren, um einen Graphen systematisch zu durchlaufen. Dabei wird von einem Startknoten $v$ aus so tief wie möglich in den Graphen vorgedrungen, bevor man zu vorangegangenen Knoten zurückkehrt (Backtracking).

Eigenschaften:

Erzeugt einen DFS-Baum (Spannbaum bei zusammenhängenden Graphen).
Konstruiert im Gegensatz zur Breitensuche keine kürzesten Pfade.
Kann zur Berechnung von Zusammenhangskomponenten genutzt werden.

Links