Що робить обхід у ширину (BFS)?

Обхід у ширину (BFS - Breadth-First Search) - це алгоритм, який поступово досліджує граф «по шарах», починаючи із заданої вершини і рухаючись спочатку до всіх її сусідів, потім до сусідів цих сусідів і так далі.

---

#Ідея

BFS шукає всі вершини, що перебувають на мінімальній відстані від початкової, перш ніж іти далі. Він використовує чергу (FIFO), щоб обробляти вершини в порядку їх відкриття.

---

#Покроково

1. Помістити стартову вершину в чергу і позначити як відвідану.
2. Поки черга не порожня:

• Витягти вершину з черги.
• Додати в чергу всіх її невідвіданих сусідів і позначити їх.

3. Повторювати, поки не обійдемо всі досяжні вершини.

---

#Приклад

Для графа:

Якщо почати з A, порядок обходу буде: A → B → D → C → E

---

#Застосування

• Пошук найкоротшого шляху в незважених графах.
• Перевірка зв'язності графа.
• Визначення рівнів (глибини) вершин.
• Пошук «хвилеподібних» зв'язків, наприклад, у задачах про поширення сигналів.

---

Підсумок: BFS - це поярусний обхід графа з використанням черги, який знаходить усі вершини в порядку їхньої «близькості» до стартової.