Motivation

BFS использует очередь (первым пришёл — первым ушёл), чтобы вершины обрабатывались в том же порядке, в котором они были обнаружены, что обеспечивает послойное исследование графа.

Зачем изучать BFS?

• Кратчайшие пути: в невзвешенном графе BFS находит путь с наименьшим количеством ребер от начальной до любой другой вершины.
• Простой и линейный: алгоритм работает за время O(V + E) с использованием очереди и маркеров посещенных вершин.
• Повсеместное применение: поиск кратчайших маршрутов в сетях, решение головоломок «словесные лестницы», прохождение лабиринтов и обход дерева по уровням — всё это задачи для BFS.

Как и в случае с DFS, мы добавляем соседей вершины в очередь в порядке возрастания, чтобы результаты были предсказуемыми.