Алгоритмы на Python

Поиск в ширину (BFS) в Python

В этом уроке вы обойдёте граф уровень за уровнем с помощью поиска в ширину и очереди deque.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Сколько шагов нужно, чтобы добраться от одного человека до другого в социальной сети или от клетки лабиринта до выхода? Поиск в ширину исследует граф кольцами, по мере удаления от старта, поэтому до каждого узла он впервые добирается по кратчайшему пути.

Пример из жизни

Поиск в ширину похож на круги на воде. Бросьте камень в начале, и волна сначала дойдёт до всего, что в одном шаге, потом до всего, что в двух шагах, и так далее. До дальних точек волна доходит только после того, как охватит все ближние.

От кругов на воде к коду
queue = deque(["A"])🪨 Бросить камень в A
node = queue.popleft()🌊 Взять следующий узел по порядку расстояния
if neighbor not in visited:🔎 Ещё не достигнут?
queue.append(neighbor)➕ Добавить его в следующее кольцо
Сначала ближайшие узлы: порядок задаёт очередь.
Одним предложением

Поиск в ширину (BFS) обходит граф уровень за уровнем от начального узла с помощью очереди, поэтому находит кратчайшие пути в графах без весов.

Главное

  1. queue хранит узлы, ждущие обработки, и первыми выдаёт те, что попали в неё раньше.
  2. visited запоминает уже найденные узлы, поэтому ни один не добавляется дважды, а из-за циклов поиск не ходит по кругу бесконечно.
  3. node = queue.popleft() берёт следующий узел; его непосещённые соседи встают в конец очереди.
  4. order показывает A, затем его соседей B и C, затем D и E уровнем дальше.

Когда это нужно?

  • Кратчайшие пути в невзвешенных графах, сетках и лабиринтах.
  • Степени разделения в социальных сетях.
  • Веб-краулеры и поиск всего, что достижимо из начальной точки.

Когда это не нужно

  • У рёбер разная стоимость, например расстояния по дорогам: используйте алгоритм Дейкстры.
  • Нужно полностью исследовать один путь до других, например для перебора с возвратом: используйте поиск в глубину.

Визуализация: Поиск в ширину (BFS) в Python

O(V + E)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Пример кода

Запустить код →
main.py
from collections import deque

graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []

while queue:
    node = queue.popleft()
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

print(order)
Получить кнопку запуска для этого примера

Результат выполнения

['A', 'B', 'C', 'D', 'E']

Разбор кода

Очередь queue хранит вершины, ожидающие посещения, и выдаёт их в том порядке, в котором они пришли. Множество visited запоминает уже встреченные вершины, чтобы не посещать одну и ту же вершину несколько раз, если в графе есть циклы. Порядок обхода A, B, C, D, E, а сложность O(V + E), где V число вершин, а E число рёбер.

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Узлы помечаются посещёнными слишком поздно

Если помечать узел только при извлечении из очереди, его можно добавить много раз.

Ошибка
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
    if neighbor not in visited:
        queue.append(neighbor)
Исправление
for neighbor in graph[node]:
    if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Далее: Поиск в глубину (DFS) в Python →

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи