BFS-vs-DFS-Visualizer

Graph-Traversal-Algorithmen werden streng durch ihre Datenstrukturabhängigkeiten definiert: Warteschlangen für die Breitensuche (Breadth-First Search, BFS) und Stapel für die Tiefensuche (Tiefensuche, DFS). BFS dehnt sich radial aus und garantiert mathematisch den kürzesten ungewichteten Pfad, während DFS vor dem rekursiven Backtracking die maximale Tiefe prüft. Die Zeitkomplexität für beide bleibt streng durch O(V + E) begrenzt. Diese deterministischen Traversalprotokolle bestimmen die Recheneffizienz der Netzwerkanalyse.

Lässt man beide nebeneinander laufen, fällt etwas auf: Sie besuchen exakt dieselben Knoten und Kanten, nur in anderer Reihenfolge. Die Breitensuche (BFS) erkundet erst die gesamte aktuelle Nachbarschaft, bevor sie weitergeht, und muss deshalb alle wartenden Knoten am Rand merken. Die Tiefensuche (DFS) folgt einem Ast und verfolgt nur den aktuellen Pfad. Fazit fürs Praktische: BFS, wenn die Antwort vermutlich nah liegt, DFS, wenn der Graph tief ist und der Speicher knapp bleiben soll.

Lange vor den Computern existierte die Tiefensuche als Regel zum Durchwandern von Labyrinthen, veröffentlicht vom französischen Mathematiker Charles Pierre Trémaux im 19. Jahrhundert. Die Breitensuche kam viel später: Edward F. Moore erfand sie 1959 in einem Aufsatz mit dem wörtlichen Titel The Shortest Path Through a Maze neu, und Konrad Zuse hatte sie schon 1945 skizziert. Zwei Grundpfeiler der Informatik, beide ursprünglich nur ersonnen, um aus einem Labyrinth herauszufinden.