Motivation
Lektion 2 von 9 im Kurs Breadth-First Search – Graph-Algorithmen von Coddy.
BFS verwendet eine Warteschlange (First-In-First-Out), sodass Knoten in genau der Reihenfolge verarbeitet werden, in der sie entdeckt werden, was die schichtweise Exploration ermöglicht.
Warum BFS lernen?
- Kürzeste Pfade: In einem ungewichteten Graphen findet BFS den Pfad mit den wenigsten Kanten vom Start zu jedem anderen Knoten.
- Einfach und linear: Es läuft in O(V + E) mit einer Warteschlange und einer "Besucht"-Markierung.
- Überall: Kürzeste Hops in Netzwerken, Wortleitern, das Lösen von Labyrinthen und die Level-Order-Traversierung von Bäumen sind allesamt BFS.
Wie bei DFS reihen wir die Nachbarn eines Knotens in aufsteigender Reihenfolge in die Warteschlange ein, damit die Ergebnisse vorhersehbar sind.
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
