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

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

Основные принципы:

1. Использует очередь (Queue): Для хранения узлов, которые нужно посетить.
2. Посещает по уровням: Обходит узлы по уровням, шаг за шагом удаляя узлы из начала очереди и добавляя их непосещенных смежных узлов в конец очереди.
3. Гарантирует нахождение кратчайшего пути: В невзвешенном графе BFS гарантирует нахождение кратчайшего пути от начального узла до любого другого достижимого узла.

Этапы выполнения:

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

Пример (обход графа):

Пусть у нас есть граф: A -> B, A -> C, B -> D, C -> E

Очередь: [] Посещенные: {}

1. Добавляем A в очередь. Помечаем A как посещенное. Очередь: [A] Посещенные: {A}
2. Очередь не пуста. Извлекаем A. Соседи A: B, C. B не посещен, C не посещен. Добавляем B в очередь, помечаем B. Добавляем C в очередь, помечаем C. Очередь: [B, C] Посещенные: {A, B, C}
3. Очередь не пуста. Извлекаем B. Соседи B: D. D не посещен. Добавляем D в очередь, помечаем D. Очередь: [C, D] Посещенные: {A, B, C, D}
4. Очередь не пуст