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

Узнайте о поиске в ширину (BFS)

Введение

Алгоритм поиска в ширину (BFS) работает на невзвешенном графе и начинается из исходной вершины $s$.

Граф может быть как ориентированным, так и неориентированным — BFS работает в обоих случаях.

Хороший способ представить BFS — как распространение огня по графу:

• на шаге $0$ “горит” только исходная вершина $s$;
• на каждом следующем шаге огонь распространяется от всех текущих горящих вершин к их соседям.

Так за одну итерацию “кольцо огня” расширяется на одно ребро. Именно поэтому BFS посещает вершины в порядке возрастания расстояния от источника.

Идея

Чтобы реализовать BFS, мы используем:

• очередь q, которая хранит вершины для обработки;
• массив used[x], который показывает, была ли вершина x уже посещена.

Изначально:

• мы помещаем исходную вершину s в очередь;
• отмечаем её как посещённую;
• отмечаем все остальные вершины как непосещённые.

Затем, пока очередь не пуста:

1. берём вершину в начале очереди;
2. проходим по всем её соседям;
3. если сосед ещё не был посещён, отмечаем его как посещённый и добавляем в очередь.

К концу алгоритма все вершины, достижимые из s, будут посещены.

Кратчайшие пути

Одно из важнейших свойств BFS состоит в том, что в невзвешенном графе он находит кратчайший путь от источника до каждой достижимой вершины.

Для этого мы можем хранить:

• — расстояние от источника до вершины ;