BFS für kürzeste ungewichtete Pfade
Berechnen Sie die Entfernung von einer Quelle Schicht für Schicht
BFS für kürzeste ungewichtete Pfade ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was BFS macht
BFS erkundet einen Graphen in Ringen: zuerst den Startknoten, dann alle Knoten in einem Schritt Entfernung, danach die Knoten in zwei Schritten Entfernung und so weiter. 🌊
Warum Ringe kürzeste Wege bedeuten
Da BFS jeden Ring vollständig abschließt, bevor der nächste beginnt, ist der erste Besuch eines Knotens immer der kürzeste ungewichtete Weg zu ihm.
Die Warteschlange ist der Motor
BFS verwendet eine Warteschlange: zuerst hinein, zuerst heraus. Neue Nachbarn werden hinten hinzugefügt und anschließend vorne verarbeitet.
from collections import deque
q = deque([start])Verfolgen, was Sie gesehen haben
Verwenden Sie eine visited-Markierung, damit Sie denselben Knoten nie zweimal in die Warteschlange einreihen. So bleibt BFS schnell und endet zuverlässig.
visited = [False] * (n + 1)
visited[start] = TrueDie Entfernung speichern
Ein dist-Array enthält die Schicht jedes Knotens. Der Startknoten erhält 0; jeder Nachbar ist um eins weiter entfernt als sein Vorgänger.
dist = [-1] * (n + 1)
dist[start] = 0Das vorderste Element entnehmen
Entnehmen Sie in jedem Schritt den Knoten am Anfang der Warteschlange. Er ist der nächste noch nicht verarbeitete Knoten und sollte daher jetzt bearbeitet werden.
u = q.popleft()Die Nachbarn erweitern
Für jeden Nachbarn von u, der noch nicht besucht wurde, setzen Sie die Markierung, bestimmen seine Entfernung und fügen ihn hinten in die Warteschlange ein.
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Die vollständige Schleife
Entnehmen und erweitern Sie Knoten so lange, wie die Warteschlange nicht leer ist. Wenn sie leer ist, haben Sie jeden erreichbaren Knoten besucht.
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Beim Einreihen markieren
Setzen Sie visited in dem Moment, in dem Sie den Knoten einreihen, nicht erst beim Entnehmen. Eine späte Markierung lässt Duplikate in die Warteschlange gelangen.
Unerreichbare Knoten bleiben -1
Jeder Knoten, bei dem nach BFS die Entfernung -1 geblieben ist, ist von Ihrem Startknoten aus einfach unerreichbar. Auch diese Information ist eine gültige Antwort.
BFS ist linear
BFS berührt jeden Knoten und jede Kante einmal und läuft daher in O(n + m). Damit werden die meisten Zeitlimits in Wettbewerbsaufgaben problemlos eingehalten.
Kurztest
Warum liefert gewöhnliches BFS kürzeste Wege?
Rückblick
Sie führen BFS mit einer Warteschlange und einem dist-Array aus: Beim Einreihen markieren, Nachbarn erweitern und am Ende die kürzesten Entfernungen ablesen. 🎉
Häufig gestellte Fragen
Ist die Lektion „BFS für kürzeste ungewichtete Pfade“ kostenlos?
Ja — der vollständige Text von „BFS für kürzeste ungewichtete Pfade“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „BFS für kürzeste ungewichtete Pfade“?
Berechnen Sie die Entfernung von einer Quelle Schicht für Schicht Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „BFS für kürzeste ungewichtete Pfade“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Adjazenzlisten aus der Eingabe
- BFS für kürzeste ungewichtete Pfade
- DFS, Rekursion und iterative Stapel
- Zusammenhängende Komponenten und Flood Fill