BFS dla najkrótszych ścieżek nieważonych
Obliczanie odległości od źródła warstwa po warstwie
BFS dla najkrótszych ścieżek nieważonych 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.
Działanie BFS
BFS przeszukuje graf warstwami: najpierw wierzchołek startowy, potem wszystkie wierzchołki oddalone o jeden krok, następnie o dwa kroki i tak dalej. 🌊
Dlaczego warstwy oznaczają najkrótszą ścieżkę
Ponieważ BFS kończy przetwarzanie każdej warstwy przed przejściem do następnej, pierwsze dotarcie do wierzchołka oznacza najkrótszą ścieżkę bez wag do tego wierzchołka.
Kolejka jest silnikiem
BFS używa kolejki działającej zgodnie z zasadą: pierwszy wchodzi, pierwszy wychodzi. Nowych sąsiadów dodaje się na końcu, a następnie przetwarza element z początku.
from collections import deque
q = deque([start])Śledzenie odwiedzonych wierzchołków
Należy przechowywać znacznik visited, aby nigdy nie dodawać tego samego wierzchołka do kolejki dwa razy. Dzięki temu BFS pozostaje szybki i kończy działanie.
visited = [False] * (n + 1)
visited[start] = TruePrzechowywanie odległości
Tablica dist przechowuje warstwę każdego wierzchołka. Wierzchołek startowy otrzymuje wartość 0, a każdy sąsiad wartość o jeden większą od swojego poprzednika.
dist = [-1] * (n + 1)
dist[start] = 0Pobieranie elementu z początku
W każdym kroku należy pobrać wierzchołek z początku kolejki. Jest to najbliższy nieprzetworzony wierzchołek, więc należy obsłużyć go właśnie teraz.
u = q.popleft()Rozwijanie sąsiadów
Dla każdego nieodwiedzonego sąsiada u należy ustawić znacznik odwiedzenia, określić jego odległość i dodać go na końcu kolejki.
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Pełna pętla
Należy pobierać elementy i rozwijać sąsiadów, dopóki kolejka nie będzie pusta. Gdy kolejka się opróżni, odwiedzone zostaną wszystkie osiągalne wierzchołki.
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Oznaczanie przy dodawaniu do kolejki
Wartość visited należy ustawić w chwili dodawania wierzchołka do kolejki, a nie podczas jego pobierania. Późne oznaczanie pozwala na pojawienie się duplikatów w kolejce.
Nieosiągalne pozostaje równe -1
Każdy wierzchołek, dla którego po zakończeniu BFS odległość nadal wynosi -1, jest po prostu nieosiągalny z wierzchołka startowego. Taki wynik również ma znaczenie.
BFS działa liniowo
BFS odwiedza każdy wierzchołek i każdą krawędź raz, więc działa w czasie O(n + m). Z łatwością mieści się to w większości limitów zadań konkursowych.
Szybkie sprawdzenie
Dlaczego zwykły BFS wyznacza najkrótsze ścieżki?
Podsumowanie
Algorytm BFS działa z kolejką i tablicą dist: oznacza wierzchołki przy dodawaniu do kolejki, rozwija sąsiadów, a po zakończeniu pozwala odczytać najkrótsze odległości. 🎉
Często zadawane pytania
Czy lekcja „BFS dla najkrótszych ścieżek nieważonych” jest bezpłatna?
Tak — pełny tekst „BFS dla najkrótszych ścieżek nieważonych” 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 „BFS dla najkrótszych ścieżek nieważonych”?
Obliczanie odległości od źródła warstwa po warstwie Ć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 „BFS dla najkrótszych ścieżek nieważonych”?
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
- Listy sąsiedztwa z danych wejściowych
- BFS dla najkrótszych ścieżek nieważonych
- DFS, rekurencja i stosy iteracyjne
- Spójne składowe i flood fill