0-1 BFS mit einer Deque
Finden Sie kürzeste Pfade bei Gewichten von 0 oder 1
0-1 BFS mit einer Deque 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.
Eine besondere Graphenart
Manche Graphen haben ausschließlich Kantengewichte von 0 oder 1. Dort können Sie Dijkstra mit einem einfacheren und schnelleren Trick übertreffen.
0-1 BFS kennenlernen
0-1 BFS findet kürzeste Wege in Graphen mit Kanten von Gewicht 0 oder 1 in linearer Zeit – ganz ohne Heap und ohne logarithmischen Faktor.
Das Werkzeug: eine Deque
Ersetzen Sie den Heap durch eine Deque, also eine Schlange, in die Sie an beiden Enden Elemente einfügen und von beiden Enden Elemente entnehmen können.
from collections import deque
dq = deque([src])Die zentrale Erkenntnis
Eine Kante mit Gewicht 0 lässt die Entfernung unverändert, während eine Kante mit Gewicht 1 sie um eins erhöht. Die Deque hält beide Gruppen in der richtigen Reihenfolge.
Bei Kanten mit Gewicht null vorne einfügen
Überqueren Sie eine Kante mit Gewicht 0? Fügen Sie den Nachbarn mit appendleft vorne ein, damit er als Nächstes verarbeitet wird, da er keine zusätzliche Entfernung verursacht.
dq.appendleft(v)Bei Kanten mit Gewicht eins hinten einfügen
Überqueren Sie eine Kante mit Gewicht 1? Fügen Sie den Nachbarn mit append hinten ein, da er eine Ebene weiter vom Startknoten entfernt liegt.
dq.append(v)Von vorne entnehmen
Entnehmen Sie den aktuellen Knoten immer mit popleft. So bleibt die Deque nach Entfernungen sortiert – genau wie bei einer schichtweisen BFS.
u = dq.popleft()Mit dem Gewicht relaxieren
Relaxieren Sie jede Kante: Die neue Entfernung ist dist[u] plus das Kantengewicht. Fügen Sie den Knoten je nach Gewicht vorne oder hinten ein.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndWarum die Reihenfolge erhalten bleibt
Die Deque enthält zu jedem Zeitpunkt höchstens zwei verschiedene Entfernungen. Diese Invariante erklärt genau, warum das Einfügen vorne oder hinten funktioniert.
Die lineare Geschwindigkeit
Da kein Heap benötigt wird, läuft 0-1 BFS in O(V + E) und ist bei demselben Graphen spürbar schneller als Dijkstra.
Wann Sie es verwenden sollten
Verwenden Sie den Algorithmus immer dann, wenn Bewegungen kostenlos sind oder eins kosten, etwa in Gittern, in denen manche Schritte blockiert und andere frei sind.
Schnelltest
Sie relaxieren einen Nachbarn über eine Kante mit Gewicht 0. Wo wird er eingefügt?
Zusammenfassung: 0-1 BFS
Mit einer Deque fügen Sie Kanten mit Gewicht 0 vorne und Kanten mit Gewicht 1 hinten ein. So erhalten Sie kürzeste Wege in sauberer O(V+E)-Zeit. ⚡
Häufig gestellte Fragen
Ist die Lektion „0-1 BFS mit einer Deque“ kostenlos?
Ja — der vollständige Text von „0-1 BFS mit einer Deque“ 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 „0-1 BFS mit einer Deque“?
Finden Sie kürzeste Pfade bei Gewichten von 0 oder 1 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 „0-1 BFS mit einer Deque“?
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
- Dijkstra mit einem Heap
- 0-1 BFS mit einer Deque
- Bellman-Ford und negative Kanten
- Floyd-Warshall für alle Paare