Що таке алгоритм BFS (пошук у першу чергу)?
Пошук із широтою в ширину (BFS) - це алгоритм, який використовується для графіку даних або пошуку дерева або обходу структур. Повною формою BFS є пошук за шириною.
Алгоритм ефективно відвідує та позначає всі ключові вузли на графіку точно в широту. Цей алгоритм вибирає один вузол (початкову або вихідну точку) на графіку, а потім відвідує всі вузли, що прилягають до вибраного вузла. Пам'ятайте, BFS отримує доступ до цих вузлів по одному.
Як тільки алгоритм відвідає і позначить початковий вузол, він рухається до найближчих невідвіданих вузлів та аналізує їх. Після відвідування всі вузли позначаються. Ці ітерації тривають до тих пір, поки всі вузли графіка не будуть успішно відвідані та позначені.
У цьому уроці з алгоритму ви дізнаєтесь:
- Що таке алгоритм BFS (пошук у першу чергу)?
- Що таке обхід графіків?
- Архітектура алгоритму BFS
- Навіщо нам алгоритм BFS?
- Як працює алгоритм 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:
- BFS використовує структуру даних черги (FIFO-First in First Out).
- Ви позначаєте будь-який вузол на графіку як кореневий і починаєте обробляти дані з нього.
- BFS проходить усі вузли на графіку і продовжує скидати їх, як завершено.
- BFS відвідує сусідній невідвіданий вузол, позначає його як зроблений і вставляє в чергу.
- Видаляє попередню вершину з черги, якщо не знайдено сусідньої вершини.
- Алгоритм BFS повторюється, поки всі вершини на графіку не будуть успішно пройдені та позначені як завершені.
- Немає циклів, спричинених BFS під час обходу даних з будь-якого вузла.
Застосування алгоритму BFS
Давайте поглянемо на деякі реальні програми, де реалізація алгоритму BFS може бути високоефективною.
- Незважені графіки: алгоритм BFS може легко створити найкоротший шлях та мінімальне дерево, що охоплює, щоб відвідати всі вершини графіка в найкоротший час з високою точністю.
- Мережі P2P: BFS може бути реалізований для пошуку всіх найближчих або сусідніх вузлів у одноранговій мережі. Це дозволить швидше знайти потрібні дані.
- Веб -сканери : Пошукові системи або веб-сканери можуть легко створити кілька рівнів індексів, використовуючи BFS. Впровадження BFS починається з джерела, яке є веб-сторінкою, а потім відвідує всі посилання з цього джерела.
- Навігаційні системи: BFS може допомогти знайти всі сусідні місця з основного або вихідного місця.
- Мережеве мовлення: Трансляційний пакет керується алгоритмом BFS, щоб знайти та досягти всіх вузлів, на які він має адресу.
Резюме
- Обхід графіка - це унікальний процес, який вимагає від алгоритму відвідування, перевірки та / або оновлення кожного окремого невідвіданого вузла в деревної структурі. Алгоритм BFS працює за подібним принципом.
- Алгоритм корисний для аналізу вузлів у графіку та побудови найкоротшого шляху обходу через них.
- Алгоритм проходить графік за найменшу кількість ітерацій і найкоротший час.
- BFS вибирає один вузол (початкову або вихідну точку) на графіку, а потім відвідує всі вузли, що прилягають до вибраного вузла. BFS отримує доступ до цих вузлів по одному.
- Відвідані та позначені дані BFS розміщує в черзі. Черга працює за принципом «перший у перший вихід». Отже, елемент, розміщений спочатку на графіку, спочатку видаляється і в результаті друкується.
- Алгоритм BFS ніколи не може потрапити в нескінченний цикл.
- Завдяки високій точності та надійній реалізації, BFS використовується в багатьох реальних рішеннях, таких як мережі P2P, веб-сканери та мережеве мовлення.