BFS исследует граф уровень за уровнем, посещая всех соседей узла перед переходом вглубь. Использует очередь и находит кратчайший путь (наименьшее количество рёбер) в невзвешенных графах.
Начните с источника, добавьте его в очередь, затем повторно извлекайте узел из очереди, посещайте его непосещённых соседей и добавляйте их в очередь. Множество visited предотвращает повторные посещения.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft() # FIFO: explore nearest first
order.append(node)
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
queue.append(nbr)
return order
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A') # -> ['A', 'B', 'C', 'D']
Используйте BFS для кратчайшего пути в невзвешенных графах, обхода по уровням и поиска связных компонент. Использует больше памяти, чем DFS (весь фронт сразу). Всегда отслеживайте visited, иначе можете зациклиться на циклах.
BFS — алгоритм для кратчайших путей, когда каждое ребро имеет одинаковый вес — маршрутизация, веб-краулинг, степени разделения в социальных сетях.
Его структура на основе очереди, уровень за уровнем, является фундаментальным паттерном обхода.
Знание BFS и DFS позволяет выбрать подходящий инструмент для задач достижимости, путей и упорядочивания.