BFS і DFS є методами обходу, що використовуються в пошуку графіка. Обхід графіка - це процес відвідування всіх вузлів графіка. Граф - це група вершин 'V' і ребер 'E', що з'єднуються з вершинами.
Діаграма порівняння
| Основа для порівняння | BFS | DFS |
|---|---|---|
| Основний | Алгоритм на основі вершин | Алгоритм на основі краю |
| Структура даних використовується для зберігання вузлів | Черга | Стек |
| Споживання пам'яті | Неефективно | Ефективний |
| Структура побудованого дерева | Широкий і короткий | Вузький і довгий |
| Мода обходу | Спочатку досліджуються найстаріші невідомі вершини. | На початку досліджуються вершини уздовж краю. |
| Оптимальність | Оптимальний для знаходження найкоротшої відстані, а не вартості. | Не оптимально |
| Застосування | Досліджується дводольний графік, пов'язаний компонент і найкоротший шлях, присутній в графі. | Досліджується дворівневий пов'язаний графік, сильно пов'язаний граф, ациклічний граф і топологічний порядок. |
Визначення BFS
Перший пошук по ширині (BFS) є методом обходу, що використовується в графіках. Він використовує чергу для зберігання відвідуваних вершин. У цьому методі підкреслюється на вершинах графа, спочатку вибирається одна вершина, потім вона відвідається і позначена. Вершини, що прилягають до відвіданої вершини, потім відвідуються і зберігаються в черзі послідовно. Аналогічно, збережені вершини обробляються один за одним, а їх сусідні вершини відвідуються. Вузол повністю вивчений перед відвідуванням будь-якого іншого вузла на графіку, іншими словами, він перетинає найменші незвідані вузли.
Приклад
Ми маємо графік, вершинами якого є A, B, C, D, E, F, G. Розглядаючи A як відправну точку. Кроки, залучені до процесу:
- Вершина А розширюється і зберігається в черзі.
- Вершини B, D і G наступники A, розширюються і зберігаються в черзі, поки Vertex A видалено.
- Тепер B на передньому кінці черги видаляється разом зі збереженням вершин E і F.
- Вершина D знаходиться на передньому кінці черги, а її підключений вузол F вже відвіданий.
- Вершина G видаляється з черги, і вона має наступника E, який вже був відвіданий.
- Тепер E і F видаляються з черги, а її наступник вершини C проходить і зберігається в черзі.
- На останньому C також видаляється і чергу порожня, що означає, що ми зробили.
- Згенерований вихідний сигнал - A, B, D, G, E, F, C.
BFS може бути корисним для пошуку, чи граф має підключені компоненти чи ні. А також він може бути використаний при виявленні дводольного графіка .
Графік є дводольним, коли вершини графа розділені на два непересічних множини; дві суміжні вершини не будуть знаходитися в одному наборі. Інший метод перевірки дводольного графіка полягає в перевірці виникнення непарного циклу на графіку. Двосторонній графік не повинен містити непарного циклу.
BFS також краще при пошуку найкоротшого шляху, на графіку можна розглядати як мережу.
Визначення DFS
Метод обходу глибини першого пошуку (DFS) використовує стек для зберігання відвідуваних вершин. DFS є методом, заснованим на краю, і працює рекурсивно, де вершини досліджуються вздовж шляху (краю). Дослідження вузла призупинено, як тільки буде знайдено інший незвіданий вузол, і найпотужніші незвідані вузли пройдуть у першу чергу. DFS проходить / відвідує кожну вершину рівно один раз і кожне ребро перевіряється рівно двічі.
Приклад
Подібно до BFS дозволяє виконувати ті ж самі графіки, що і для виконання операцій DFS.
- Розглядаючи A як початкову вершину, яка досліджується і зберігається в стеку.
- B послідовність вершини A зберігається в стеку.
- Вершина B має два послідовності E і F, серед яких алфавітно E досліджується спочатку і зберігається в стеку.
- Наступник вершини E, тобто G зберігається в стеку.
- Вершина G має дві пов'язані вершини, і обидва вже відвідані, так що G виривається з стека.
- Аналогічно, E s також видаляється.
- Тепер вершина B знаходиться у верхній частині стека, її інший вузол (вершина) F досліджується і зберігається в стеку.
- Вершина F має два наступники C і D, між якими C спочатку проходить і зберігається в стеку.
- У вершині C є тільки один попередник, який вже був відвіданий, тому його вилучають зі стека.
- Тепер вершина D, підключена до F, відвідується і зберігається в стеку.
- Оскільки вершина D не має жодних невідкритих вузлів, то D видаляється.
- Аналогічно, F, B і A також з'являються.
- Згенерований вихід - A, B, E, G, F, C, D.
Застосування DFS включає в себе перевірку двох крайових зв'язних графів, сильно пов'язаних графа, ациклічного графа і топологічного порядку .
Граф називається двома ребрами, приєднаними тоді і тільки тоді, коли він залишається з'єднаним, навіть якщо один з його ребер видалено. Ця програма дуже корисна в комп'ютерних мережах, де відмова однієї ланки в мережі не вплине на решту мережі, і вона все одно буде підключена.
Сильно пов'язаний граф - це графік, в якому повинен існувати шлях між впорядкованою парою вершин. DFS використовується в спрямованому графі для пошуку шляху між кожною впорядкованою парою вершин. DFS може легко вирішувати проблеми з підключенням.
Ключові відмінності між BFS і DFS
- BFS є вершинним алгоритмом, а DFS - крайовим алгоритмом.
- У BFS використовується структура даних черги. З іншого боку, DFS використовує стек або рекурсію.
- Простір пам'яті ефективно використовується в DFS, тоді як використання простору в BFS не є ефективним.
- BFS є оптимальним алгоритмом, в той час як DFS не є оптимальним.
- DFS будує вузькі і довгі дерева. На відміну від BFS будує широке і коротке дерево.
Висновок
BFS і DFS, обидві методи пошуку графа мають подібний час роботи, але різне споживання простору, DFS приймає лінійний простір, тому що ми повинні пам'ятати один шлях з невивченими вузлами, а BFS зберігає всі вузли в пам'яті.
DFS дає більш глибокі розв'язки і не є оптимальним, але добре працює, коли рішення є щільним, тоді як BFS є оптимальним, який спочатку шукає оптимальну мету.
