0-1 BFS с деком
Находите кратчайшие пути при весах 0 или 1
«0-1 BFS с деком» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Особый вид графа
В некоторых графах веса рёбер равны только 0 или 1. Для них существует более простой и быстрый приём, чем алгоритм Дейкстры.
Знакомьтесь: 0-1 BFS
0-1 BFS находит кратчайшие пути в графах с весами 0 и 1 за линейное время, без кучи и множителя log.
Инструмент: дек
Замените кучу на дек — очередь, в которую можно добавлять элементы и из которой можно извлекать их с обоих концов.
from collections import deque
dq = deque([src])Главная идея
Ребро с весом 0 сохраняет то же расстояние, а ребро с весом 1 добавляет единицу. Дек поддерживает обе группы в нужном порядке.
Нулевые рёбра — в начало
Перешли по ребру с весом 0? Используйте appendleft, чтобы добавить соседнюю вершину в начало: дополнительная стоимость отсутствует.
dq.appendleft(v)Рёбра с весом 1 — в конец
Перешли по ребру с весом 1? Используйте append, чтобы добавить соседнюю вершину в конец: она находится на один слой дальше от исходной вершины.
dq.append(v)Извлекайте из начала
Всегда используйте popleft для извлечения текущей вершины. Так дек остаётся отсортированным по расстоянию, как при послойном обходе BFS.
u = dq.popleft()Выполняйте релаксацию с учётом веса
Расслабьте каждое ребро: новое расстояние равно dist[u] плюс вес ребра, после чего добавьте вершину в начало или конец в зависимости от этого веса.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndПочему порядок сохраняется
В деке одновременно находятся не более двух различных расстояний. Именно этот инвариант объясняет, почему добавление в начало и конец работает.
Линейная скорость
Поскольку куча не используется, 0-1 BFS работает за O(V + E), заметно быстрее алгоритма Дейкстры на том же графе.
Когда его использовать
Используйте этот алгоритм, когда переходы бесплатны или стоят единицу, например на сетках, где одни шаги заблокированы, а другие доступны.
Быстрая проверка
Вы выполнили релаксацию соседа через ребро с весом 0. Куда его добавить?
Повторение: 0-1 BFS
С помощью дека добавляйте рёбра с весом 0 в начало, а рёбра с весом 1 — в конец. Так Вы получаете кратчайшие пути за чистое время O(V+E). ⚡
Изучай Coding Interview Prep с ИИ-репетитором — бесплатно
Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.
- Курсы
- 90
- Уроки
- 360
Часто задаваемые вопросы
Урок «0-1 BFS с деком» бесплатный?
Да — полный текст урока «0-1 BFS с деком» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «0-1 BFS с деком»?
Находите кратчайшие пути при весах 0 или 1 Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «0-1 BFS с деком»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Алгоритм Дейкстры с кучей
- 0-1 BFS с деком
- Беллман — Форд и отрицательные рёбра
- Алгоритм Флойда — Уоршелла для всех пар