Поиск в ширину (BFS) в Python
В этом уроке вы обойдёте граф уровень за уровнем с помощью поиска в ширину и очереди deque.
Введение
Какую задачу это решает
Сколько шагов нужно, чтобы добраться от одного человека до другого в социальной сети или от клетки лабиринта до выхода? Поиск в ширину исследует граф кольцами, по мере удаления от старта, поэтому до каждого узла он впервые добирается по кратчайшему пути.
Пример из жизни
Поиск в ширину похож на круги на воде. Бросьте камень в начале, и волна сначала дойдёт до всего, что в одном шаге, потом до всего, что в двух шагах, и так далее. До дальних точек волна доходит только после того, как охватит все ближние.
queue = deque(["A"])🪨 Бросить камень в Anode = queue.popleft()🌊 Взять следующий узел по порядку расстоянияif neighbor not in visited:🔎 Ещё не достигнут?queue.append(neighbor)➕ Добавить его в следующее кольцоПоиск в ширину (BFS) обходит граф уровень за уровнем от начального узла с помощью очереди, поэтому находит кратчайшие пути в графах без весов.
Главное
queueхранит узлы, ждущие обработки, и первыми выдаёт те, что попали в неё раньше.visitedзапоминает уже найденные узлы, поэтому ни один не добавляется дважды, а из-за циклов поиск не ходит по кругу бесконечно.node = queue.popleft()берёт следующий узел; его непосещённые соседи встают в конец очереди.orderпоказывает A, затем его соседей B и C, затем D и E уровнем дальше.
Когда это нужно?
- Кратчайшие пути в невзвешенных графах, сетках и лабиринтах.
- Степени разделения в социальных сетях.
- Веб-краулеры и поиск всего, что достижимо из начальной точки.
Когда это не нужно
- У рёбер разная стоимость, например расстояния по дорогам: используйте алгоритм Дейкстры.
- Нужно полностью исследовать один путь до других, например для перебора с возвратом: используйте поиск в глубину.
Визуализация: Поиск в ширину (BFS) в Python
O(V + E)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
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.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Узлы помечаются посещёнными слишком поздно
Если помечать узел только при извлечении из очереди, его можно добавить много раз.
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)
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Средне
- Tree Diameter A tree is a connected undirected graph with no cycles. Средне
- Count Islands Count groups of connected land cells in a grid. Средне