Як черга використовується в BFS (пошук у ширину)?

В алгоритмі BFS (Breadth-First Search, пошук у ширину) черга використовується для зберігання вершин, які потрібно відвідати в порядку їх відкриття.

#Суть BFS

Алгоритм обходить граф шарами: спочатку всі вершини, що перебувають на відстані 1 від початкової, потім на відстані 2, і так далі.

#Роль черги

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

• вилучається вершина з початку черги (dequeue),
• усі її невідвідані сусіди додаються в кінець черги (enqueue).

3. Цей процес триває, поки всі досяжні вершини не будуть оброблені.

#Чому саме черга

Черга гарантує порядок FIFO: усі вершини одного рівня обробляються раніше, ніж вершини наступного.

Саме тому BFS проходить граф по шарах, на відміну від DFS, який використовує стек і йде в глибину.