Пошук у ширину (BFS)
Обходить граф шар за шаром. Яку вершину брати далі, вирішує черга, тож найближчі вершини завжди відвідуються першими.
- час O(V + E)
- пам'ять O(V)
- використовує чергу
Що це означає?
- Вершина: точка графа, тут намальована як кружечок із літерою.
- Ребро: лінія, що з'єднує дві вершини. Тут ним можна пройти в обидва боки.
- Сусіди: вершини, з'єднані з даною вершиною ребром. Їх переглядають в алфавітному порядку.
- Черга: хто перший прийшов, той перший вийшов. BFS завжди бере вершину, яка чекає найдовше.
- Стек: хто останнім прийшов, той першим вийшов. DFS завжди продовжує з вершини, до якої дійшов останньою.
- V і E: кількість вершин і ребер. O(V + E) означає, що кожну вершину й кожне ребро обробляють сталу кількість разів.
- у черзі
- поточна
- готова
- ребро дерева пошуку
- пропущене ребро
Починаємо з вершини A. Натисніть «Відтворити» або проходьте пошук крок за кроком.
Пробіл: відтворення або пауза. Стрілки ліворуч і праворуч: крок. Home і End: на початок або в кінець.
Спробуйте: Оберіть граф із двох частин. До вершин, не з'єднаних зі стартом, пошук ніколи не дійде.
Як це працює
BFS ставить початкову вершину в чергу. Потім раз за разом бере вершину з початку черги й додає її нових сусідів у кінець. Черга обслуговує в порядку надходження, тож кожна вершина на відстані одного ребра готова раніше за будь-яку вершину на відстані двох. Число біля вершини - це її відстань від старту: найменша кількість ребер, якими до неї можна дійти.
Коли варто використовувати
BFS потрібен, коли треба знайти найкоротший шлях у кроках: найменше ходів у головоломці, найменше переходів у мережі, друзів і друзів друзів. На великому графі черга може сильно вирости, бо тримає цілий шар одразу.