Алгоритм пошуку в ширину (BFS) із ПРИКЛАДОМ
Сара Чен
⚡ Розумний підсумок
Пошук у ширину (BFS) – це алгоритм, який проходить граф рівень за рівнем, відвідуючи всіх сусідів вузла, перш ніж рухатися вглиб. Він використовує чергу FIFO та знаходить найкоротший шлях у незважених графах без нескінченних циклів.
Що таке алгоритм BFS (пошук у ширину)?
Пошук у ширину (BFS) – це алгоритм, який використовується для побудови графіків даних, пошуку по дереву чи обходу структур. Повна форма BFS – це пошук у ширину.
Алгоритм ефективно відвідує та точно позначає всі ключові вузли на графіку. Цей алгоритм вибирає один вузол (початкову або вихідну точку) на графіку, а потім відвідує всі вузли, суміжні з вибраним вузлом. Пам’ятайте, що BFS отримує доступ до цих вузлів один за іншим.
Як тільки алгоритм відвідує та позначає початковий вузол, він рухається до найближчих невідвіданих вузлів і аналізує їх. Після відвідування всі вузли позначаються. Ці ітерації тривають, доки всі вузли графа не будуть успішно відвідані та позначені.
Що таке обхід графа?
Обхід графа — це широко використовувана методологія для визначення позиції вершини в графі. Це розширений алгоритм пошуку, який може швидко й точно аналізувати граф разом із позначенням послідовності відвіданих вершин. Цей процес дає змогу швидко відвідувати кожен вузол на графіку, не замикаючись у нескінченному циклі.
Архітектура алгоритму BFS
- На різних рівнях даних ви можете позначити будь-який вузол як початковий або початковий вузол для початку проходження. BFS відвідає вузол, позначить його як відвіданий та помістить його в чергу.
- Тепер BFS відвідає найближчі та невідвідані вузли та позначить їх. Ці значення також додаються до черги. Черга працює на Модель FIFO.
- Аналогічним чином, решта найближчих та невідвіданих вузлів на графі аналізуються, позначаються та додаються до черги. Ці елементи видаляються з черги в міру їх надходження та друкуються як результат.
Для чого нам потрібен алгоритм BFS?
Існує безліч причин використовувати алгоритм BFS для пошуку в наборі даних. Деякі з найважливіших аспектів, які роблять цей алгоритм вашим першим вибором:
- BFS корисний для аналізу вузлів у графі та побудови найкоротшого шляху проходження через них.
- BFS може пройти через граф за найменшу кількість ітерацій.
- Архітектура алгоритму BFS проста та надійна.
- Результат алгоритму BFS має високий рівень точності в порівнянні з іншими алгоритмами.
- Ітерації BFS безперебійні, і немає можливості, щоб цей алгоритм потрапив у проблему нескінченного циклу.
Як працює алгоритм BFS?
Обхід графа вимагає від алгоритму відвідування, перевірки та/або оновлення кожного окремого невідвіданого вузла в деревоподібній структурі. Обходи графа класифікуються за порядком, у якому вони відвідують вузли на графіку.
Алгоритм BFS починає операцію з першого або початкового вузла на графі та повністю його проходить. Після того, як він успішно проходить початковий вузол, наступна вершина на графі, яка не була пройдена, відвідується та позначається.
Отже, можна сказати, що всі вузли, суміжні з поточною вершиною, відвідуються та проходять у першій ітерації. Для реалізації роботи алгоритму BFS використовується проста методологія черг, яка складається з таких кроків:
Крок 1)
Кожна вершина або вузол у графі відома. Наприклад, ви можете позначити вузол як V.
Крок 2)
Якщо доступ до вершини V не здійснюється, тоді додайте вершину V до черги BFS.
Крок 3)
Розпочніть пошук BFS, і після завершення позначте вершину V як відвідану.
Крок 4)
Черга BFS ще не порожня, тому видаліть вершину V графа з черги.
Крок 5)
Знайдіть усі вершини графа, що залишилися, які суміжні з вершиною V.
Крок 6)
Для кожної суміжної вершини, скажімо V1, якщо вона ще не відвідана, тоді додаємо V1 до черги BFS.
Крок 7)
BFS відвідає V1, позначить його як відвіданий та видалить з черги.
Приклад алгоритму BFS
Крок 1)
У вас є графік із семи чисел у діапазоні від 0 до 6.
Крок 2)
0 або нуль було позначено як кореневий вузол.
Крок 3)
0 відвідується, позначається та вставляється в структуру даних черги.
Крок 4)
Решта суміжних з 0 та невідвіданих вузлів відвідуються, позначаються та вставляються до черги.
Крок 5)
Ітерації обходу повторюються, доки не будуть відвідані всі вузли.
Правила алгоритму BFS
Ось важливі правила використання алгоритму BFS:
- Черга (FIFO – «перший прийшов, перший вийшов») структура даних використовується BFS.
- Ви позначаєте будь-який вузол у графі як корінь і починаєте переглядати дані з нього.
- BFS проходить через усі вузли графа та зберігає відкинуті елементи.ping їх як завершені.
- BFS відвідує сусідній невідвіданий вузол, позначає його як виконаний і вставляє в чергу.
- Він видаляє попередню вершину з черги, якщо сусідня вершина не знайдена.
- Алгоритм BFS виконує ітерації, доки всі вершини графа не будуть успішно пройдені та позначені як завершені.
- Немає петель, викликаних BFS під час проходження даних з будь-якого вузла.
Застосування алгоритму BFS
Давайте подивимося на деякі з реальних програм, де реалізація алгоритму BFS може бути дуже ефективною.
- Незважені графіки: Алгоритм BFS може легко створити найкоротший шлях та мінімальне остовне дерево, щоб відвідати всі вершини графа за найкоротший можливий час з високою точністю.
- Мережі P2P: BFS можна реалізувати для визначення місцезнаходження всіх найближчих або сусідніх вузлів у одноранговій мережі. Це дозволить швидше знаходити необхідні дані.
- Веб-сканери: Пошукові системи або веб-сканери можуть легко створити кілька рівнів індексів, використовуючи BFS. Реалізація BFS починається з джерела, яким є веб-сторінка, а потім відвідує всі посилання з цього джерела.
- Навігаційні системи: BFS може допомогти знайти всі сусідні місця з основного або вихідного розташування.
- Мережеве мовлення: Пакет, який транслюється, керується алгоритмом BFS, щоб знайти та досягти всіх вузлів, для яких він має адресу.
