Різниця між BFS та DFS

BFS проти DFS

Перший пошук по ширині (також відомий як BFS) - це метод пошуку, який використовується для розширення всіх вузлів певного графіка. Він виконує це завдання шляхом пошуку кожного окремого рішення з метою вивчення та розширення цих вузлів (або комбінації їх послідовностей). Таким чином, BFS не використовує евристичний алгоритм (або алгоритм, який шукає рішення за допомогою декількох сценаріїв). Після отримання всіх вузлів вони додаються до черги, відомої як черга First In, First Out. Ті вузли, які не були досліджені, "зберігаються" в контейнері, позначеному "відкритим"; Після вивчення їх транспортують до контейнера з позначкою "закрито".

Перший глибинний пошук (також відомий як DFS) - це метод пошуку, який закопується вглиб дочірнього вузла пошуку до досягнення мети (або до тих пір, поки не буде вузла без будь-яких інших перестановок чи «дітей»). Після того, як знайдена одна мета, пошук здійснює зворотний пошук до попереднього вузла, який був вирішений, повторюючи процес, поки всі вузли не були успішно виконані. Таким чином, вузли продовжують відкладатися для подальшої розвідки - це називається нерекурсивною реалізацією.

Особливостями BFS є просторова і часова складність, повнота, доказ повноти та оптимальності. Космічна складність означає пропорцію кількості вузлів на найглибшому рівні пошуку. Часова складність відноситься до фактичної кількості "часу", що використовується для розгляду кожного шляху, який буде проходити вузол у пошуку. Повнота - це, по суті, пошук, який знаходить рішення в графіку незалежно від типу графа. Доказом повноти є найменший рівень, на якому мета виявляється у вузлі на певній глибині. Нарешті, оптимальність стосується BFS, який не зважується - це графік, що використовується для одиничної вартості.

DFS - це найприродніший вихід із використанням розтягнутого дерева - це дерево, що складається з усіх вершин і деяких ребер у непрямому графіку. У цьому формуванні графік поділяється на три класи: Вперед ребра, що вказують від вузла до дочірнього вузла; задні краї, спрямовані від вузла до більш раннього вузла; і поперечні краї, які не роблять жодного з цих.

Підсумок:

1. BFS здійснює пошук кожного рішення в графі, щоб розширити його вузли; DFS закопується вглиб дочірнього вузла до досягнення мети.

2. Особливості системи BFS - складність простору та часу, повнота, доказ повноти та оптимальності; Найбільш природним результатом для DFS є дерево, що охоплює три класи: передні краї, задні краї та поперечні краї.