Алгоритм пошуку в ширину (BFS) із ПРИКЛАДОМ

Що таке алгоритм BFS (пошук у ширину)?

Пошук у ширину (BFS) — це алгоритм, який використовується для побудови даних у вигляді графіків або пошуку дерева чи обходу структур. Повною формою BFS є пошук у ширину.

Алгоритм ефективно відвідує та точно позначає всі ключові вузли на графіку. Цей алгоритм вибирає один вузол (початкову або вихідну точку) на графіку, а потім відвідує всі вузли, суміжні з вибраним вузлом. Пам’ятайте, що BFS отримує доступ до цих вузлів один за іншим.

Як тільки алгоритм відвідує та позначає початковий вузол, він рухається до найближчих невідвіданих вузлів і аналізує їх. Після відвідування всі вузли позначаються. Ці ітерації тривають, доки всі вузли графа не будуть успішно відвідані та позначені.

Що таке обхід графа?

Обхід графа — це широко використовувана методологія для визначення позиції вершини в графі. Це розширений алгоритм пошуку, який може швидко й точно аналізувати граф разом із позначенням послідовності відвіданих вершин. Цей процес дає змогу швидко відвідувати кожен вузол на графіку, не замикаючись у нескінченному циклі.

Архітектура алгоритму BFS

1. На різних рівнях даних ви можете позначити будь-який вузол як початковий або початковий вузол для початку обходу. BFS відвідає вузол, позначить його як відвіданий і розмістить у черзі.
2. Тепер BFS відвідає найближчі та невідвідані вузли та позначає їх. Ці значення також додаються до черги. Черга працює на Модель FIFO.
3. Таким же чином решта найближчих і невідвіданих вузлів на графіку аналізуються, позначаються та додаються до черги. Ці елементи видаляються з черги під час отримання та друкуються як результат.

Для чого нам потрібен алгоритм 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-First in First Out) структура даних використовується BFS.
• Ви позначаєте будь-який вузол на графіку як кореневий і починаєте проходити з нього дані.
• BFS обходить усі вузли на графі та продовжує відкидати їх як завершені.
• BFS відвідує сусідній невідвіданий вузол, позначає його як виконаний і вставляє в чергу.
• Видаляє попередню вершину з черги, якщо не знайдено сусідньої вершини.
• Алгоритм BFS повторюється, доки всі вершини в графі не будуть успішно пройдені та позначені як завершені.
• Немає петель, викликаних BFS під час проходження даних з будь-якого вузла.

Застосування алгоритму BFS

Давайте подивимося на деякі з реальних програм, де реалізація алгоритму BFS може бути дуже ефективною.

• Незважені графіки: Алгоритм BFS може легко створити найкоротший шлях і мінімальне остовне дерево для відвідування всіх вершин графа за найкоротший час з високою точністю.
• Мережі P2P: BFS може бути реалізований для визначення місцезнаходження всіх найближчих або сусідніх вузлів у одноранговій мережі. Це дозволить швидше знайти потрібні дані.
• Веб-сканери: Пошукові системи або веб-сканери можуть легко створити кілька рівнів індексів, використовуючи BFS. Реалізація BFS починається з джерела, яким є веб-сторінка, а потім відвідує всі посилання з цього джерела.
• Навігаційні системи: BFS може допомогти знайти всі сусідні місця з основного або вихідного розташування.
• Мережеве мовлення: Пакет, який транслюється, керується алгоритмом BFS, щоб знайти та досягти всіх вузлів, для яких він має адресу.

Підсумки

• Обхід графа – це унікальний процес, який вимагає від алгоритму відвідування, перевірки та/або оновлення кожного окремого невідвіданого вузла в деревоподібній структурі. Алгоритм BFS працює за аналогічним принципом.
• Алгоритм корисний для аналізу вузлів у графі та побудови найкоротшого шляху проходження через них.
• Алгоритм обходить граф за найменшу кількість ітерацій і за найкоротший час.
• BFS вибирає один вузол (початкову або вихідну точку) на графіку, а потім відвідує всі вузли, суміжні з вибраним вузлом. BFS отримує доступ до цих вузлів один за одним.
• Відвідані та позначені дані розміщуються в черзі BFS. Черга працює за принципом «перший прийшов, перший вийшов». Отже, елемент, розміщений на графіку першим, видаляється першим і друкується як результат.
• Алгоритм BFS ніколи не може потрапити в нескінченний цикл.
• Завдяки високій точності та надійній реалізації BFS використовується в багатьох реальних рішеннях, таких як мережі P2P, веб-сканери та мережеве мовлення.