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