Informatik Algorithmen – Breiten- und Tiefensuche

DFS erkundet einen Pfad so tief wie möglich, bevor sie zurückkehrt (Backtracking), nutzt dafür einen Stack (LIFO) oder Rekursion.

BFS nutzt eine Queue (First-In-First-Out), um Knoten in der Reihenfolge ihrer Entdeckung zu verarbeiten und Schichten korrekt abzuarbeiten.

Die iterative DFS verwendet einen expliziten Stack (Last-In-First-Out), um den zuletzt entdeckten Knoten als nächstes zu verarbeiten.

BFS läuft in O(|V| + |E|) für Adjazenzlisten, da jeder Knoten und jede Kante maximal einmal besucht wird.

DFS benötigt ebenfalls O(|V| + |E|) für Adjazenzlisten, da jeder Knoten und jede Kante einmal bearbeitet wird.

BFS speichert im schlimmsten Fall alle Knoten einer Ebene: O(|V|) Speicher, bei breiten Graphen oft mehr als DFS.

DFS speichert nur den aktuellen Pfad: O(|V|) im schlimmsten Fall (tiefer Pfad), bei tiefen Graphen oft weniger als BFS.

BFS liefert in ungewichteten Graphen garantiert den kürzesten Pfad (minimale Kantenanzahl) vom Start- zum Zielknoten.

DFS eignet sich für Zyklusdetektion, topologische Sortierung, zusammenhängende Komponenten und das Erkunden aller Pfade in tiefen Graphen.

DFS markiert Knoten als 'in Bearbeitung' (grau); trifft sie auf einen grauen Knoten, liegt ein Rückkantenzug und damit ein Zyklus vor.

DFS backtracket automatisch beim Erreichen eines Endknotens oder toten Endes; BFS backtracket nicht, da es schichtweise parallel expandiert.

BFS wählt man für kürzeste Pfade in ungewichteten Graphen, Level-Order-Traversierung und wenn der Zielknoten nah am Start liegt.

DFS wählt man bei tiefen Graphen, geringerem Speicherbedarf, topologischer Sortierung, Zyklusdetektion und wenn vollständige Pfadexploration nötig ist.

Rekursive DFS nutzt den Call-Stack implizit, iterative DFS einen expliziten Stack; beide sind äquivalent, rekursiv oft kürzer, iterativ steuerbarer.