Поиск в ширину

---

Поиск в ширину (англ. breadth-first search, BFS) — один из методов обхода графа. Пусть задан граф ${\displaystyle G=(V,E)}$ и выделена исходная вершина ${\displaystyle s}$. Алгоритм поиска в ширину систематически обходит все ребра ${\displaystyle G}$ для «открытия» всех вершин, достижимых из ${\displaystyle s}$, вычисляя при этом расстояние (минимальное количество рёбер) от ${\displaystyle s}$ до каждой достижимой из ${\displaystyle s}$ вершины. Алгоритм работает как для ориентированных, так и для неориентированных графов.^[1]

Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии ${\displaystyle k+1}$, выполняется обход вершин на расстоянии ${\displaystyle k}$.

Поиск в ширину работает путём последовательного просмотра отдельных уровней графа, начиная с узла-источника ${\displaystyle u}$.

Рассмотрим все рёбра ${\displaystyle (u,v)}$, выходящие из узла ${\displaystyle u}$. Если очередной узел ${\displaystyle v}$ является целевым узлом, то поиск завершается; в противном случае узел ${\displaystyle v}$ добавляется в очередь. После того, как будут проверены все рёбра, выходящие из узла ${\displaystyle u}$, из очереди извлекается следующий узел ${\displaystyle u}$, и процесс повторяется.

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

Ниже приведён псевдокод алгоритма для случая, когда необходимо лишь найти целевой узел. В зависимости от конкретного применения алгоритма, может потребоваться дополнительный код, обеспечивающий сохранение нужной информации (расстояние от начального узла, узел-родитель и т. п.)

---