BFS для кратчайших невзвешенных путей
Расстояние от источника по уровням
«BFS для кратчайших невзвешенных путей» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что делает BFS
BFS исследует граф слоями: сначала стартовую вершину, затем всё, что находится в одном шаге от неё, потом в двух шагах и так далее. 🌊
Почему слои дают кратчайший путь
Поскольку BFS полностью обрабатывает каждый слой перед переходом к следующему, первое посещение вершины даёт кратчайший путь до неё в невзвешенном графе.
Очередь — основной механизм
BFS использует очередь: первым вошёл — первым вышел. Новых соседей добавляют в конец, а следующим обрабатывают элемент в начале.
from collections import deque
q = deque([start])Отслеживание посещённых вершин
Храните отметку посещённости, чтобы никогда не добавлять одну и ту же вершину в очередь дважды. Это сохраняет быстродействие BFS и не даёт обходу зациклиться.
visited = [False] * (n + 1)
visited[start] = TrueСохранение расстояния
Массив расстояний хранит слой каждой вершины. Для стартовой вершины расстояние равно 0, а для каждого соседа — на единицу больше, чем у родительской вершины.
dist = [-1] * (n + 1)
dist[start] = 0Извлечение из начала
На каждом шаге извлекайте вершину из начала очереди. Это ближайшая ещё не обработанная вершина, поэтому обработайте её сейчас.
u = q.popleft()Расширение по соседям
Для каждого соседа вершины u, которого ещё не посещали, установите отметку посещения, задайте расстояние и добавьте его в конец очереди.
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Полный цикл
Продолжайте извлекать вершины и расширять обход, пока очередь не станет пустой. Когда очередь опустеет, все достижимые вершины будут посещены.
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Отмечайте при добавлении в очередь
Устанавливайте отметку посещённости в момент добавления вершины в очередь, а не при извлечении. Поздняя отметка позволяет дубликатам попасть в очередь.
Недостижимая вершина остаётся равной -1
Любая вершина, для которой после BFS расстояние по-прежнему равно -1, просто недостижима из начальной вершины. Это тоже содержательный результат.
BFS работает за линейное время
BFS посещает каждую вершину и каждое ребро один раз, поэтому работает за O(n + m). Этого легко хватает для большинства ограничений в задачах соревнований.
Быстрая проверка
Почему обычный BFS находит кратчайшие пути?
Повторение
Вы запускаете BFS с очередью и массивом расстояний: отмечаете вершины при добавлении в очередь, расширяете обход по соседям и после завершения считываете кратчайшие расстояния. 🎉
Часто задаваемые вопросы
Урок «BFS для кратчайших невзвешенных путей» бесплатный?
Да — полный текст урока «BFS для кратчайших невзвешенных путей» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «BFS для кратчайших невзвешенных путей»?
Расстояние от источника по уровням Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «BFS для кратчайших невзвешенных путей»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Списки смежности из входных данных
- BFS для кратчайших невзвешенных путей
- DFS, рекурсия и итеративные стеки
- Связные компоненты и заливка