0-1 BFS med en deque
Korteste stier når vektene er 0 eller 1
0-1 BFS med en deque er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
En spesiell type graf
Noen grafer har bare kantvekter på 0 eller 1. Da kan du slå Dijkstra med et enklere og raskere triks.
Møt 0-1 BFS
0-1 BFS finner korteste veier i grafer med kanter med vekt 0 eller 1 på lineær tid, uten heap og uten noen log-faktor.
Verktøyet: en deque
Bytt ut heapen med en deque, en kø som du kan legge til i og ta ut fra både foran og bak.
from collections import deque
dq = deque([src])Den sentrale innsikten
En kant med vekt 0 beholder den samme avstanden, mens en kant med vekt 1 legger til én. Dequen holder begge gruppene i riktig rekkefølge.
Foran for kanter med vekt 0
Går du over en kant med vekt 0? Bruk appendleft for å legge naboen først, slik at den behandles deretter, siden den ikke gir noen ekstra avstand.
dq.appendleft(v)Bak for kanter med vekt 1
Går du over en kant med vekt 1? Bruk append for å legge naboen bakerst, fordi den ligger ett lag lenger fra startnoden.
dq.append(v)Ta ut fra fronten
Ta alltid ut den aktuelle noden med popleft. Da holder dequen seg sortert etter avstand, akkurat som i en BFS lag for lag.
u = dq.popleft()Relakser med vekten
Relakser hver kant: Den nye avstanden er dist[u] pluss kantvekten. Legg deretter noden foran eller bak avhengig av vekten.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndHvorfor den forblir sortert
Dequen inneholder høyst to forskjellige avstander om gangen. Denne invarianten er nettopp grunnen til at plassering foran og bak fungerer.
Den lineære hastigheten
Siden det ikke brukes noen heap, bruker 0-1 BFS O(V + E), og er merkbart raskere enn Dijkstra på den samme grafen.
Når du bør bruke den
Bruk den når bevegelser er gratis eller koster én, for eksempel i rutenett der noen steg er blokkert og andre er åpne.
Hurtigsjekk
Du relakserer en nabo over en kant med vekt 0. Hvor skal den legges?
Oppsummering: 0-1 BFS
Med en deque legger du kanter med vekt 0 foran og kanter med vekt 1 bak. Da får du korteste veier på ren O(V+E)-tid. ⚡
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «0-1 BFS med en deque» gratis?
Ja – hele teksten i «0-1 BFS med en deque» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «0-1 BFS med en deque»?
Korteste stier når vektene er 0 eller 1 Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «0-1 BFS med en deque»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Dijkstra med en heap
- 0-1 BFS med en deque
- Bellman-Ford og negative kanter
- Floyd-Warshall for alle par