BFS-vs-DFS-Visualizer

Beobachte, wie BFS und DFS denselben Graphen unterschiedlich erkunden. BFS geht in die Breite, DFS geht in die Tiefe.

Startwerte — BFS-vs-DFS-Visualizer

Graph-Vorlage	4×4-Gitter
Startknoten	0

Ändere oben einen Regler, und die Ergebnisse werden neu berechnet.

Interaktive Simulation wird geladen...

BFS findet den kürzesten Weg nur, wenn alle Kanten gleich viel kosten 🖖

Der übliche Grund, BFS zu wählen, ist die Garantie des kürzesten Wegs. Diese Garantie ist schmaler, als sie klingt: sie gilt, weil BFS jede Kante als einen Schritt behandelt, sodass ein Knoten beim ersten Erreichen zwangsläufig über die geringstmögliche Anzahl Sprünge gefunden wurde. Kommen echte Kosten ins Spiel — Streckenlängen, Umsteigegebühren, Latenz —, verschwindet die Garantie. BFS antwortet weiterhin selbstbewusst, aber falsch: ein Weg mit zwei teuren Kanten kann leicht mehr kosten als einer mit fünf günstigen. Dijkstras Algorithmus ist die Korrektur, und er ist fast genau das: BFS, bei dem die einfache Warteschlange durch eine Prioritätswarteschlange ersetzt wird.

Gleiche Karte, zwei Reisestile 🖖

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.

Beide Algorithmen wurden in Labyrinthen geboren 🖖

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.

GRAPHDURCHLAUF — WELCHE REIHENFOLGE BRAUCHST DU, UND WAS KOSTET SIE DICH?

In welchem Durchlauf-Fall bist du?

BFS und DFS besuchen dieselben Knoten und unterscheiden sich in einer Codezeile: Warteschlange statt Stapel. Alles Weitere folgt daraus. Die Warteschlange breitet sich in Ringen aus, deshalb hat BFS beim ersten Erreichen eines Knotens den Weg mit den wenigsten Kanten genommen. Der Stapel taucht ab, deshalb ist DFS früher am fernen Ende — nur auf keinem bestimmten Weg. Was du brauchst, hängt von der Frage ab und von der Form des Graphen, die entscheidet, was beides kostet.

Du brauchst die wenigsten Kanten — BFS, denn es besucht in Abstandsschichten FIFO ⇒ min |E|

Ein Baum — Ebenenordnung gegen Präorder, und die Speicherkosten drehen sich um BFS: O(w), DFS: O(d)

Eine Kette — beide Reihenfolgen fallen zusammen, die Wahl wird gleichgültig deg ≤ 2 ⇒ BFS = DFS

Nicht alles ist erreichbar — ein Startknoten genügt nicht c(G) > 1

Du brauchst die wenigsten Kanten — BFS, denn es besucht in Abstandsschichten

Was du weißt: Ein ungewichteter Graph und eine Frage nach dem kürzesten Weg. BFS besucht erst alles im Abstand 1, dann alles im Abstand 2 — die erste Ankunft an einem Knoten liegt also auf einem kürzesten Weg.

Regel: FIFO ⇒ min |E|

Rechenbeispiel: Im 4×4-Gitter ab Knoten 0 besucht BFS 0, 1, 4, 2, 5, 8, 3, 6, 9, 12, … — eine diagonale Wellenfront. DFS besucht 0, 1, 2, 3, 7, 6, 5, 4, … und erreicht Knoten 4 erst im achten Schritt.

Diesen Fall öffnen: 4×4-Gitter

Du brauchst die wenigsten Kanten — BFS, denn es besucht in Abstandsschichten. BFS zieht in Abstandsschichten nach außen; DFS schlängelt sich erst einen Gang hinunter. Ein ungewichteter Graph und eine Frage nach dem kürzesten Weg. BFS besucht erst alles im Abstand 1, dann alles im Abstand 2 — die erste Ankunft an einem Knoten liegt also auf einem kürzesten Weg. — BFS zieht in Abstandsschichten nach außen; DFS schlängelt sich erst einen Gang hinunter.

Ein Baum — Ebenenordnung gegen Präorder, und die Speicherkosten drehen sich um

Was du weißt: Im Baum haben beide Reihenfolgen Namen: BFS ist die Ebenenordnung, DFS die Präorder. Beide besuchen alle 15 Knoten; verschieden ist nur, wie viel gleichzeitig gehalten werden muss.

Regel: BFS: O(w), DFS: O(d)

Rechenbeispiel: BFS liefert 0, 1, 2, 3, …, 14 — Ebene für Ebene. DFS liefert 0, 1, 3, 7, 8, 4, 9, 10, 2, … — zuerst das linke Rückgrat hinunter. Spitzenwert der Warteschlange 8, des Stapels 4.

Diesen Fall öffnen: Binärbaum

Ein Baum — Ebenenordnung gegen Präorder, und die Speicherkosten drehen sich um. Die Ebenenordnung füllt jede Zeile, bevor sie tiefer geht; die Präorder läuft bis zum Blatt und kehrt um. Im Baum haben beide Reihenfolgen Namen: BFS ist die Ebenenordnung, DFS die Präorder. Beide besuchen alle 15 Knoten; verschieden ist nur, wie viel gleichzeitig gehalten werden muss. — Die Ebenenordnung füllt jede Zeile, bevor sie tiefer geht; die Präorder läuft bis zum Blatt und kehrt um.

Eine Kette — beide Reihenfolgen fallen zusammen, die Wahl wird gleichgültig

Was du weißt: Jeder Knoten hat genau einen unbesuchten Nachbarn, es gibt also nur einen Weg vorwärts. BFS und DFS erzeugen dieselbe Folge und halten jeweils einen Knoten.

Regel: deg ≤ 2 ⇒ BFS = DFS

Rechenbeispiel: In der Kette aus 12 Knoten besuchen beide 0, 1, 2, …, 11 in dieser Reihenfolge, und beide Fronten bleiben durchgehend bei Größe 1.

Diesen Fall öffnen: Lange Kette

Eine Kette — beide Reihenfolgen fallen zusammen, die Wahl wird gleichgültig. Ohne Verzweigung laufen beide Durchläufe dieselbe Linie in derselben Reihenfolge ab. Jeder Knoten hat genau einen unbesuchten Nachbarn, es gibt also nur einen Weg vorwärts. BFS und DFS erzeugen dieselbe Folge und halten jeweils einen Knoten. — Ohne Verzweigung laufen beide Durchläufe dieselbe Linie in derselben Reihenfolge ab.

Nicht alles ist erreichbar — ein Startknoten genügt nicht

Was du weißt: Der Graph zerfällt in Teile. Von einem Knoten aus besucht jeder Durchlauf nur die Komponente, zu der dieser Knoten gehört, und hört dann auf.

Regel: c(G) > 1

Rechenbeispiel: Von Knoten 0 des Zehn-Knoten-Graphen besuchen BFS und DFS jeweils genau 4 Knoten und halten an. Die Knoten 4, 5, 6, 7, 8 und 9 werden nie berührt.

Diesen Fall öffnen: Unzusammenhängend

Nicht alles ist erreichbar — ein Startknoten genügt nicht. Vier Knoten erreichbar, sechs nicht: Ein Start erkundet eine Komponente und nicht mehr. Der Graph zerfällt in Teile. Von einem Knoten aus besucht jeder Durchlauf nur die Komponente, zu der dieser Knoten gehört, und hört dann auf. — Vier Knoten erreichbar, sechs nicht: Ein Start erkundet eine Komponente und nicht mehr.

Quellen (2)

Insight block 3 — BFS as a maze algorithm: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.
Trémaux's rule, as it was actually published: É. Lucas, Récréations mathématiques, vol. 1. Gauthier-Villars, Paris, 1882 — Lucas credits the maze-walking procedure to Charles Pierre Trémaux.

Aufgabe vollständig gelöst

Ein Durchlauf eines Labyrinths mit 16 Knoten und 16 Kanten 5 Schritte
Das Labyrinth enthält 16 Knoten, die durch 16 Kanten verbunden sind. Bestimmen Sie, wie viele Knoten eine Traversierung ausgehend von Knoten 0 erreicht und wie weit Knoten 15 von Knoten 0 entfernt ist. Dies ist der Zustand Labyrinth-Korridor mit Startknoten 0.
1. Schreiben Sie das Labyrinth als Adjazenzliste auf, bevor Sie irgendetwas anderes tun. Knoten 4 ist derjenige, der beachtet werden sollte: Keine einzige Kante berührt ihn, sein Grad ist also 0 und keine an einer anderen Stelle beginnende Traversierung wird jemals auf ihm landen.
  
  $0 : 11 : 0, 2, 52 : 1, 33 : 24 : \emptyset 5 : 1, 6, 96 : 5, 7, 107 : 6, 118 : 9, 12 9 : 5, 8, 1010 : 6, 9, 1411 : 7, 15 12 : 8, 1313 : 12, 1414 : 10, 1315 : 11$
2. Die Breitensuche sortiert das Erreichbare in Schichten, wobei Schicht k alles enthält, worauf man von Schicht k − 1 aus zuerst trifft. Das Aufbauen dieser Schichten ist eher eine Hüllenbildung als ein Laufweg – eine Schicht wird vollständig abgeschlossen, bevor die nächste geöffnet wird, und kein Knoten erscheint zweimal.
  
  $L_{0} L_{3} L_{6} = {0} = {3, 6, 9} = {13, 15} L_{1} L_{4} = {1} = {7, 8, 10} L_{2} L_{5} = {2, 5} = {11, 12, 14}$
3. Addieren Sie die Schichtgrößen. Die Traversierung erreicht 15 Knoten, einen weniger als die 16, die der Graph enthält, und deshalb stoppt der Schrittzähler eins unter der Knotenzahl.
  
  $1 + 1 + 2 + 3 + 3 + 3 + 2 = 15, n = 16, de g (4) = 0$
4. Knoten 15 erscheint zuerst in Schicht 6, und eine Schichtnummer ist ein Abstand: Ein Knoten wird immer nur von einem Knoten eine Schicht darüber in die Warteschlange eingereiht, sodass nichts in Schicht 6 in weniger als 6 Kanten erreicht werden kann. Die Route 0-1-5-6-7-11-15 erreicht 6, die Schranke ist also exakt.
  
  $15 \in L_{6} ⟹ d (0, 15) = 6 : 0 \to 1 \to 5 \to 6 \to 7 \to 11 \to 15$
5. Für die Tiefensuche gibt es keine solche Invariante. Nimmt der Suchlauf am Knoten 1 zuerst 5 statt 2, dann am Knoten 5 zuerst 9 statt 6 und schließlich am Knoten 9 zuerst 8 statt 10, so sind das jeweils zulässige Entscheidungen zwischen noch nicht besuchten Nachbarknoten. Damit legt er sich auf den langen Korridor fest und kehrt erst um, wenn es im Graphen nicht mehr weitergeht. Am anderen Ende erreicht er Knoten 15 über einen Weg mit 12 Kanten. Für die Frage nach der Erreichbarkeit ist dieser Weg eine vollkommen gültige Antwort.
  
  $0 \to 1 \to 5 \to 9 \to 8 \to 12 \to 13 \to 14 \to 10 \to 6 \to 7 \to 11 \to 15 ⟹ ℓ = 12$
Antwort

Knoten 15 liegt 6 Kanten vom Start entfernt, und ein Tiefensuchlauf kann Ihnen eine Route der Länge 12 an denselben Ort liefern. Der Faktor 2 ist nicht der interessante Teil; von Bedeutung ist vielmehr, woher eine Abkürzung überhaupt kommen kann. Die erreichbare Komponente enthält 15 Knoten, sodass jeder ihrer Spannbäume 14 Kanten nutzt – und das Labyrinth hat 16, was bedeutet, dass genau 2 Kanten überschüssig sind. Löscht man diese 2, ist der Rest ein Baum, in dem es zwischen jedem Knotenpaar genau einen Pfad gibt, sodass die beiden Panels dann bei jedem Abstand übereinstimmen und sich nur in der Reihenfolge ihres Durchlaufs unterscheiden. Jede Uneinigkeit über Abstände zwischen ihnen geht auf diese 2 zusätzlichen Kanten zurück. Dies ist auch der Grund, warum die Tiefensuche die günstigere Angewohnheit ist, wenn die Frage nur lautet, ob ein Knoten erreichbar ist, und die falsche, sobald die Frage lautet, wie weit.

$∣ E ∣ - (∣ V ∣ - 1) = 16 - (15 - 1) = 2$

Vom 42Math-Team · Aktualisiert 2026-07-27

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

4×4-Gitter - 4×4-Gitter: BFS durchsucht Schicht für Schicht
Labyrinthgang - Labyrinthgang
Sterngraph - Neun Speichen, jeder Knoten einen Sprung vom Zentrum entfernt. Die Tiefensuche kann nirgends in die Tiefe gehen und liefert dir deshalb dieselbe Reihenfolge wie die Breitensuche.
Lange Kette - Zwölf Knoten in einer Reihe: Die Reihenfolgen stimmen wieder überein. Hier speichert jeder Algorithmus jedoch jeweils nur einen Knoten, im Gegensatz zu den neun beim Stern.
Binärbaum - Binärbaum: DFS geht in die Tiefe, bevor es in die Breite geht
Unzusammenhängend - Zwei Quadrate und zwei isolierte Knoten. Ein Durchlauf ab Knoten 0 erreicht 4 der 10, und auch mit noch so viel Suchen findest du den Rest nicht.
Dichter Graph - Dichter Graph: viele Kanten, ähnliche Reihenfolgen