DFSbasierte

DFSbasierte Algorithmen verwenden die Tiefensuche (DFS) als zentrales Suchmuster für Graphen. Sie besuchen Knoten rekursiv oder mithilfe eines Stacks und verfolgen Pfade so lange, bis kein Weiteres mehr möglich ist, bevor sie zurückkehren und andere Äste erkunden.

In der Praxis werden Datenstrukturen wie Adjazenzlisten, ein Visited-Array und ein Stack eingesetzt. Die Komplexität einer DFS-Operation liegt allgemein bei O(V+E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten eines Graphen bezeichnet. DFS eignet sich sowohl für gerichtete als auch für ungerichtete Graphen.

Wichtige Anwendungen umfassen das Finden stark zusammenhängender Komponenten (Tarjan, Kosaraju), Topologische Sortierung, Zyklenerkennung, Ermittlung von Brücken und Schnittpunkten sowie das Generieren von Tiefenspannbäumen. DFS dient auch der Mazensuche und der Strukturaufarbeitung in Compiler- und Programmanalyse-Tools.

Vorteile einer DFS-basierten Herangehensweise sind die effiziente vollständige Durchquerung von Graphen mit oft moderatem Speicherbedarf, insbesondere bei dünn besetzten Graphen. Nachteile umfassen, dass DFS nicht notwendigerweise kürzeste Pfade liefert und bei sehr tief verschachtelten Graphen Stack-Overflow-Risiken bestehen können. Eine iterative Implementierung oder Tail-Recursion-Optimierung kann dem entgegenwirken.

Im Vergleich zu BFS verbindet DFS eher Tiefen- mit Strukturaufdeckung und eignet sich besonders gut für die Ermittlung von Komponenten, Topologien und anderen Graphstrukturen. BFS eignet sich hingegen typischerweise besser für kürzeste Pfade und Ebenenabhängigkeiten. In vielen Anwendungen ergänzen sich beide Ansätze.