Що таке обхід дерева в глибину (DFS)?

Обхід дерева в глибину (DFS, Depth-First Search) - це спосіб обходу дерева, за якого алгоритм іде вглиб по гілці, поки не досягне кінця (листка), і лише потім повертається назад, щоб пройти інші гілки.

---

#Принцип

1. Починаємо з кореня.
2. Ідемо по першому доступному нащадку вниз до самого кінця.
3. Коли далі йти не можна - повертаємось до попереднього вузла.
4. Продовжуємо, поки не будуть відвідані всі вузли.
5. Для реалізації зазвичай використовується стек (LIFO), явно або через рекурсію.

---

#Приклад

Можливі типи обходу (варіанти DFS):

• Pre-order (прямий): A, B, D, E, C
• In-order (симетричний): D, B, E, A, C
• Post-order (зворотний): D, E, B, C, A

---

#Особливості DFS

• Використовує стек або рекурсію.
• Добре підходить для задач, де потрібно дослідити всю структуру або знайти шлях углиб.
• Може працювати швидше за BFS, якщо потрібний елемент перебуває глибоко в дереві.

---

#Підсумок

DFS - це обхід дерева вглиб гілок, за якого кожна гілка досліджується повністю, перш ніж перейти до наступної. Реалізується через стек або рекурсію і має три основні порядки обходу: pre-, in-, post-order.