Что такое алгоритм поиска в ширину?

Алгоритм поиска в ширину (BFS - Breadth-First Search) — это алгоритм обхода или поиска по дереву или графу. Он начинает с корневого узла (или произвольного узла, если граф не дерево) и исследует всех его непосредственных соседей, затем исследует соседей этих соседей и так далее, уровень за уровнем. BFS реализуется с использованием очереди.

Принцип работы:

1. Поместить начальный узел в очередь.
2. Пока очередь не пуста:
   • Извлечь узел из очереди.
   • Если узел является искомым, остановить поиск.
   • Иначе, поместить всех его не посещенных соседей в очередь и пометить их как посещенные.

Характеристики:

• Полнота: Гарантирует нахождение решения, если оно существует.
• Оптимальность: Находит кратчайший путь в невесомом графе (где веса рёбер равны).
• Сложность по времени: Зависит от структуры графа, для E рёбер и V вершин — O(V + E).
• Сложность по памяти: O(V) в худшем случае, та