0-1 BFS z deque
Najkrótsze ścieżki przy wagach 0 lub 1
0-1 BFS z deque to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Szczególny rodzaj grafu
Niektóre grafy mają wyłącznie krawędzie o wagach 0 lub 1. W takim przypadku algorytm Dijkstry można zastąpić prostszą i szybszą metodą.
Poznaj 0-1 BFS
0-1 BFS znajduje najkrótsze ścieżki w grafach z wagami 0/1 w czasie liniowym, bez kopca i bez czynnika logarytmicznego.
Narzędzie: deque
Zamiast kopca należy użyć deque, czyli kolejki, do której można dodawać elementy i z której można je pobierać z obu końców.
from collections import deque
dq = deque([src])Najważniejsza obserwacja
Krawędź o wadze 0 nie zmienia odległości, natomiast krawędź o wadze 1 zwiększa ją o jeden. Deque utrzymuje obie grupy we właściwej kolejności.
Przód dla krawędzi o wadze zero
Przejście przez krawędź o wadze 0? Sąsiada należy dodać metodą appendleft, aby został przetworzony jako następny, ponieważ nie zwiększa odległości.
dq.appendleft(v)Tył dla krawędzi o wadze jeden
Przejście przez krawędź o wadze 1? Sąsiada należy dodać metodą append na końcu, ponieważ znajduje się o jedną warstwę dalej od źródła.
dq.append(v)Pobieranie z przodu
Zawsze należy pobierać bieżący wierzchołek metodą popleft. Dzięki temu deque pozostaje uporządkowany według odległości, podobnie jak w warstwowym BFS.
u = dq.popleft()Relaksacja z uwzględnieniem wagi
Należy wykonać relaksację każdej krawędzi: obliczyć nową odległość jako dist[u] plus waga krawędzi, a następnie dodać wierzchołek z przodu lub z tyłu, zależnie od tej wagi.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndDlaczego kolejność zostaje zachowana
Deque zawiera jednocześnie najwyżej dwie różne odległości. Ta niezmiennicza własność wyjaśnia, dlaczego dodawanie elementów z przodu i z tyłu działa.
Liniowy czas działania
Ponieważ nie ma kopca, 0-1 BFS działa w czasie O(V + E), zauważalnie szybciej niż Dijkstra dla tego samego grafu.
Kiedy go używać
Należy go używać zawsze, gdy ruchy są bezpłatne albo kosztują jeden, na przykład na siatkach, gdzie niektóre przejścia są zablokowane, a inne dostępne.
Krótki test
Wykonano relaksację sąsiada przez krawędź o wadze 0. Gdzie należy go umieścić?
Podsumowanie: 0-1 BFS
Za pomocą deque krawędzie o wadze 0 dodaje się z przodu, a krawędzie o wadze 1 z tyłu. W ten sposób otrzymuje się najkrótsze ścieżki w przejrzystym czasie O(V+E). ⚡
Często zadawane pytania
Czy lekcja „0-1 BFS z deque” jest bezpłatna?
Tak — pełny tekst „0-1 BFS z deque” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „0-1 BFS z deque”?
Najkrótsze ścieżki przy wagach 0 lub 1 Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „0-1 BFS z deque”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Algorytm Dijkstry ze stosem kopcowym
- 0-1 BFS z deque
- Bellman-Ford i ujemne krawędzie
- Floyd-Warshall dla wszystkich par