BFS проти DFS – різниця між ними
Ключова різниця між BFS і DFS
- BFS знаходить найкоротший шлях до місця призначення, тоді як DFS переходить до нижньої частини піддерева, а потім повертається назад.
- Повною формою BFS є пошук у ширину, а повною формою DFS є пошук у глибину.
- BFS використовує чергу, щоб відстежувати наступне місце для відвідування. тоді як DFS використовує стек для відстеження наступного місця відвідування.
- BFS проходить відповідно до рівня дерева, тоді як DFS обходить відповідно до глибини дерева.
- BFS реалізовано за допомогою списку FIFO; з іншого боку, DFS реалізується за допомогою списку LIFO.
- У BFS ви ніколи не потрапите в скінченні цикли, тоді як у DFS ви можете потрапити в нескінченні цикли.
Що таке BFS?
BFS — це алгоритм, який використовується для побудови графів даних або пошуку дерева чи обходу структур. Алгоритм ефективно відвідує та точно позначає всі ключові вузли на графіку.
Цей алгоритм вибирає один вузол (початкову або вихідну точку) на графіку, а потім відвідує всі вузли, суміжні з вибраним вузлом. Після того, як алгоритм відвідує і позначає початковий вузол, він рухається до найближчих невідвіданих вузлів і аналізує їх.
Після відвідування всі вузли позначаються. Ці ітерації тривають, доки всі вузли графа не будуть успішно відвідані та позначені. Повною формою BFS є пошук у ширину.
Що таке DFS?
DFS — це алгоритм для пошуку або обходу графів або дерев у напрямку глибини. Виконання алгоритму починається з кореневого вузла та досліджує кожну гілку перед поверненням назад. Він використовує стекову структуру даних для запам’ятовування, отримання наступної вершини та початку пошуку, коли на будь-якій ітерації з’являється тупик. Повною формою DFS є пошук у глибину.
Різниця між двійковим деревом BFS і DFS
Ось важливі відмінності між BFS і DFS.
BFS | ДФС |
---|---|
BFS знаходить найкоротший шлях до місця призначення. | DFS переходить до нижньої частини піддерева, а потім повертається назад. |
Повна форма BFS – пошук у ширину. | Повною формою DFS є Depth First Search. |
Він використовує чергу, щоб відстежувати наступне місце для відвідування. | Він використовує стек, щоб відстежувати наступне місце для відвідування. |
BFS обходить відповідно до рівня дерева. | DFS обходить відповідно до глибини дерева. |
Реалізовано за допомогою списку FIFO. | Реалізовано за допомогою списку LIFO. |
Він вимагає більше пам'яті порівняно з DFS. | Він вимагає менше пам'яті порівняно з BFS. |
Цей алгоритм дає рішення з найменшим шляхом. | Цей алгоритм не гарантує вирішення найменшого шляху. |
У BFS немає необхідності повертатися назад. | Існує потреба у зворотному відстеженні в DFS. |
Ви ніколи не потрапите в пастку кінцевих циклів. | Ви можете потрапити в нескінченні петлі. |
Якщо ви не знайдете жодної мети, можливо, вам доведеться розширити багато вузлів, перш ніж буде знайдено рішення. | Якщо ви не знайдете жодної мети, може виникнути зворотне відстеження листового вузла. |
Приклад BFS
У наступному прикладі BFS ми використали граф із 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
Ось додатки BFS:
Незважені графіки
Алгоритм BFS може легко створити найкоротший шлях і мінімальне остовне дерево для відвідування всіх вершин графа за найкоротший час з високою точністю.
Мережі P2P
BFS може бути реалізований для визначення місцезнаходження всіх найближчих або сусідніх вузлів у одноранговій мережі. Це дозволить швидше знайти потрібні дані.
Веб-сканери
Пошукові системи або веб-сканери можуть легко створити кілька рівнів індексів, використовуючи BFS. Реалізація BFS починається з джерела, яким є веб-сторінка, а потім відвідує всі посилання з цього джерела.
Мережеве мовлення
Пакет, який транслюється, керується алгоритмом BFS, щоб знайти та досягти всіх вузлів, для яких він має адресу.
Застосування DFS
Ось важливі програми DFS:
Зважений графік
У зваженому графі обхід графа DFS генерує дерево найкоротших шляхів і мінімальне остовне дерево.
Виявлення циклу в графі
Граф має цикл, якщо ми знайшли заднє ребро під час DFS. Тому нам слід запустити DFS для графіка та перевірити наявність задніх країв.
Пошук шляху
Ми можемо спеціалізуватися на алгоритмі DFS для пошуку шляху між двома вершинами.
Топологічне сортування
Він в основному використовується для планування завдань із заданих залежностей серед групи завдань. В інформатиці він використовується для планування інструкцій, серіалізації даних, логічного синтезу, визначення порядку завдань компіляції.
Пошук сильно зв'язаних компонентів графа
Він використовується в графі DFS, коли існує шлях від кожної вершини графа до інших вершин, що залишилися.
Розгадування головоломок лише одним рішенням
Алгоритм DFS можна легко адаптувати для пошуку всіх рішень лабіринту, включаючи вузли на існуючому шляху в відвіданий набір.