Що таке BFS?
BFS - це алгоритм, який використовується для графіку даних, пошуку дерева або обходу структур. Алгоритм ефективно відвідує та позначає всі ключові вузли на графіку точно в широту.
Цей алгоритм вибирає один вузол (початкову або вихідну точку) на графіку, а потім відвідує всі вузли, що прилягають до вибраного вузла. Як тільки алгоритм відвідає і позначить початковий вузол, він рухається до найближчих невідвіданих вузлів та аналізує їх.
Після відвідування всі вузли позначаються. Ці ітерації тривають до тих пір, поки всі вузли графіка не будуть успішно відвідані та позначені. Повною формою BFS є пошук за шириною.
У цьому BSF Vs. Підручник з бінарного дерева DFS, ви дізнаєтесь:
- Що таке BFS?
- Що таке DFS?
- Приклад BFS
- Приклад DFS
- Різниця між бінарним деревом BFS та DFS
- Застосування BFS
- Застосування DFS
Що таке DFS?
DFS - це алгоритм пошуку або обходу графіків або дерев у напрямку глибини. Виконання алгоритму починається з кореневого вузла і досліджує кожну гілку перед зворотним відстеженням. Він використовує структуру даних стеку для запам'ятовування, отримання наступної вершини та для початку пошуку, коли в будь-якій ітерації з'являється тупик. Повною формою DFS є пошук по глибині.
Приклад BFS
У наступному прикладі DFS ми використовували графік, що має 6 вершин.
Приклад BFS
Крок 1)
У вас є графік із семи чисел в діапазоні від 0 до 6.
Крок 2)
0 або нуль позначено як кореневий вузол.
Крок 3)
0 відвідано, позначено та вставлено в структуру даних черги.
Крок 4)
Залишилися 0 сусідніх та невідвіданих вузлів відвідуються, розмічаються та вставляються в чергу.
Крок 5)
Ітерації обходу повторюються, поки не будуть відвідані всі вузли.
Приклад DFS
У наступному прикладі DFS ми використали неорієнтований графік, що має 5 вершин.
Крок 1)
Ми почали з вершини 0. Алгоритм починається з введення її в список відвідувань та одночасного розміщення всіх сусідніх вершин у структурі даних, що називається стеком.
Крок 2)
Ви відвідаєте елемент, який знаходиться у верхній частині стека, наприклад, 1, і перейдете до сусідніх вузлів. Це тому, що 0 вже відвідали. Тому ми відвідуємо вершину 2.
Крок 3)
Вершина 2 має неповершену сусідню вершину в 4. Тому ми додаємо це в стек і відвідуємо його.
Крок 4)
Нарешті, ми відвідаємо останню вершину 3, вона не має будь-яких невідвіданих суміжних вузлів. Ми завершили обхід графіка за допомогою алгоритму DFS.
Різниця між бінарним деревом BFS та DFS
| BFS | DFS |
| BFS знаходить найкоротший шлях до пункту призначення. | DFS переходить до нижньої частини піддерева, а потім повертається назад. |
| Повною формою BFS є пошук по ширині. | Повною формою DFS є Depth First Search. |
| Він використовує чергу для відстеження наступного місця для відвідування. | Він використовує стек для відстеження наступного місця для відвідування. |
| BFS проходить відповідно до рівня дерева. | DFS проходить по глибині дерева. |
| Він реалізований за допомогою списку FIFO. | Він реалізований за допомогою списку LIFO. |
| Це вимагає більше пам'яті порівняно з DFS. | Це вимагає менше пам'яті порівняно з BFS. |
| Цей алгоритм дає найменше рішення шляху. | Цей алгоритм не гарантує найменшого рішення шляху. |
| У BFS немає необхідності зворотного відстеження. | Існує потреба у зворотному відстеженні в DFS. |
| Ви ніколи не потрапите в кінцеві петлі. | Ви можете потрапити в нескінченні петлі. |
| Якщо ви не знайшли жодної цілі, можливо, вам доведеться розширити багато вузлів, перш ніж рішення буде знайдено. | Якщо ви не знайдете жодної цілі, може відбутися зворотне відстеження вузлів листя. |
Застосування BFS
Ось програми BFS:
Незважені графіки:
Алгоритм BFS може легко створити найкоротший шлях та мінімальне дерево, що охоплює, щоб відвідати всі вершини графіка в найкоротший час з високою точністю.
Мережі P2P:
BFS може бути реалізований для пошуку всіх найближчих або сусідніх вузлів у одноранговій мережі. Це дозволить швидше знайти потрібні дані.
Веб-сканери:
Пошукові системи або веб-сканери можуть легко створити кілька рівнів індексів, використовуючи BFS. Впровадження BFS починається з джерела, яке є веб-сторінкою, а потім відвідує всі посилання з цього джерела.
Мережеве мовлення:
Трансляційний пакет керується алгоритмом BFS, щоб знайти та досягти всіх вузлів, для яких він має адресу.
Застосування DFS
Ось важливі програми DFS:
Зважений графік:
У зваженому графіку обхід графіку DFS генерує дерево найкоротшого шляху та мінімальне охоплююче дерево.
Виявлення циклу в графіку:
Графік має цикл, якщо ми знайшли задній край під час DFS. Тому нам слід запустити DFS для графіка та перевірити наявність зворотних країв.
Пошук шляху:
Ми можемо спеціалізуватися на алгоритмі DFS для пошуку шляху між двома вершинами.
Топологічне сортування:
Він в основному використовується для планування завдань із заданих залежностей серед групи завдань. В інформатиці він використовується при плануванні інструкцій, серіалізації даних, логічному синтезі, визначенні порядку завдань компіляції.
Пошук міцно пов’язаних компонентів графіка:
Він використовується в графі DFS, коли є шлях від кожної вершини в графі до інших вершин, що залишилися.
Розв’язування головоломок лише одним рішенням:
Алгоритм DFS можна легко адаптувати для пошуку всіх рішень лабіринту, включивши вузли на існуючий шлях у відвіданий набір.
ОСНОВНІ ВІДМІННОСТІ:
- BFS знаходить найкоротший шлях до пункту призначення, тоді як DFS йде до нижньої частини піддерева, а потім повертається назад.
- Повною формою BFS є пошук по ширині, тоді як повна форма DFS - пошук по глибині.
- BFS використовує чергу, щоб відстежувати наступне місце відвідування. тоді як DFS використовує стек для відстеження наступного місця для відвідування.
- BFS проходить по рівню дерева, тоді як DFS проходить по глибині дерева.
- BFS реалізований за допомогою списку FIFO, з іншого боку, DFS реалізований за допомогою списку LIFO.
- У BFS ви ніколи не потрапите в кінцеві цикли, тоді як у DFS ви можете потрапити в нескінченні цикли.