Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке обхід дерева в глибину (DFS)?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**DFS (Depth-First Search)** - це спосіб обходу дерева, за якого алгоритм іде вглиб по гілці, поки не досягне кінця (листка), і лише потім повертається назад, щоб пройти інші гілки. **Ключове:** DFS реалізується через стек або рекурсію і має три основні порядки обходу: pre-, in-, post-order.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення**Обхід дерева в глибину (DFS, Depth-First Search)** - це спосіб обходу дерева, за якого алгоритм іде **вглиб по гілці**, поки не досягне кінця (листка), і лише потім повертається назад, щоб пройти інші гілки. --- ## Принцип 1. Починаємо з **кореня**. 2. Ідемо по першому доступному нащадку **вниз до самого кінця**. 3. Коли далі йти не можна - **повертаємось** до попереднього вузла. 4. Продовжуємо, поки не будуть відвідані всі вузли. 5. Для реалізації зазвичай використовується **стек (LIFO)**, явно або через **рекурсію**. --- ## Приклад ```javascript A / \ B C / \ D E ``` Можливі типи обходу (варіанти 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.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.