BFS проти DFS – різниця між ними

Ключова різниця між BFS і DFS

  • BFS знаходить найкоротший шлях до місця призначення, тоді як DFS переходить до нижньої частини піддерева, а потім повертається назад.
  • Повною формою BFS є пошук у ширину, а повною формою DFS є пошук у глибину.
  • BFS використовує чергу, щоб відстежувати наступне місце для відвідування. тоді як DFS використовує стек для відстеження наступного місця відвідування.
  • BFS проходить відповідно до рівня дерева, тоді як DFS обходить відповідно до глибини дерева.
  • BFS реалізовано за допомогою списку FIFO; з іншого боку, DFS реалізується за допомогою списку LIFO.
  • У BFS ви ніколи не потрапите в скінченні цикли, тоді як у DFS ви можете потрапити в нескінченні цикли.
Різниця між BFS і DFS
Різниця між 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)

Приклад BFS

У вас є графік із семи чисел у діапазоні від 0 до 6.

Крок 2)

Приклад BFS

0 або нуль було позначено як кореневий вузол.

Крок 3)

Приклад BFS

0 відвідується, позначається та вставляється в структуру даних черги.

Крок 4)

Приклад BFS

Решта 0 суміжних і невідвіданих вузлів відвідуються, позначаються та вставляються в чергу.

Крок 5)

Приклад BFS

Ітерації обходу повторюються, доки не будуть відвідані всі вузли.

Приклад DFS

У наступному прикладі DFS ми використали неорієнтований граф із 5 вершинами.

Приклад DFS

Крок 1)

Приклад DFS

Ми почали з вершини 0. Алгоритм починається з розміщення її у списку відвіданих і одночасного розміщення всіх її суміжних вершин у структура даних називається стеком.

Крок 2)

Приклад DFS

Ви відвідаєте елемент, який знаходиться у верхній частині стека, наприклад, 1, і перейдете до його сусідніх вузлів. Це тому, що 0 вже відвідано. Тому відвідуємо вершину 2.

Крок 3)

Приклад DFS

Вершина 2 має невідвідану сусідню вершину в 4. Тому ми додаємо її в стек і відвідуємо її.

Крок 4)

Приклад DFS

Нарешті, ми відвідаємо останню вершину 3, вона не має невідвіданих суміжних вузлів. Ми завершили обхід графа за допомогою алгоритму DFS.

Приклад DFS

Застосування BFS

Ось додатки BFS:

Незважені графіки

Алгоритм BFS може легко створити найкоротший шлях і мінімальне остовне дерево для відвідування всіх вершин графа за найкоротший час з високою точністю.

Мережі P2P

BFS може бути реалізований для визначення місцезнаходження всіх найближчих або сусідніх вузлів у одноранговій мережі. Це дозволить швидше знайти потрібні дані.

Веб-сканери

Пошукові системи або веб-сканери можуть легко створити кілька рівнів індексів, використовуючи BFS. Реалізація BFS починається з джерела, яким є веб-сторінка, а потім відвідує всі посилання з цього джерела.

Мережеве мовлення

Пакет, який транслюється, керується алгоритмом BFS, щоб знайти та досягти всіх вузлів, для яких він має адресу.

Застосування DFS

Ось важливі програми DFS:

Зважений графік

У зваженому графі обхід графа DFS генерує дерево найкоротших шляхів і мінімальне остовне дерево.

Виявлення циклу в графі

Граф має цикл, якщо ми знайшли заднє ребро під час DFS. Тому нам слід запустити DFS для графіка та перевірити наявність задніх країв.

Пошук шляху

Ми можемо спеціалізуватися на алгоритмі DFS для пошуку шляху між двома вершинами.

Топологічне сортування

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

Пошук сильно зв'язаних компонентів графа

Він використовується в графі DFS, коли існує шлях від кожної вершини графа до інших вершин, що залишилися.

Розгадування головоломок лише одним рішенням

Алгоритм DFS можна легко адаптувати для пошуку всіх рішень лабіринту, включаючи вузли на існуючому шляху в відвіданий набір.