Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що робить обхід у глибину (DFS)?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Обхід у глибину (DFS)** - це алгоритм, який досліджує граф максимально глибоко по кожному шляху, перш ніж повернутися назад. **Ключове:** DFS - це пошук «у глибину» з поверненням назад, який обходить граф, ідучи шляхом до кінця, перш ніж перейти до інших гілок.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення**Обхід у глибину (DFS - Depth-First Search)** - це алгоритм, який **досліджує граф максимально глибоко по кожному шляху**, перш ніж повернутися назад. --- ### Ідея DFS іде «вглиб», від стартової вершини до першого сусіда, потім до сусіда сусіда і так далі, поки не досягне вершини, у якої більше немає невідвіданих сусідів. Потім він **повертається (backtrack)** і продовжує з інших вершин. --- ### Покроково (рекурсивна версія) 1. Почати зі стартової вершини і позначити її як відвідану. 2. Для кожного сусіда цієї вершини: - Якщо сусід не відвіданий, запустити DFS для нього. 3. Продовжувати, поки не обійдемо всі досяжні вершини. --- ### Приклад Для графа ```javascript A - B - C | | D - E ``` Якщо почати з **A**, можливий порядок обходу: **A → B → C → E → D** (Точний порядок залежить від порядку сусідів у структурі даних.) --- ### Реалізація - Використовує **стек (Stack)**, неявно через рекурсію або явно через структуру даних. --- ### Застосування - Перевірка **зв'язності** графа. - Пошук **циклів**. - **Топологічне сортування** (в орієнтованих графах). - Пошук шляхів, компонент зв'язності, «островів» тощо. --- **Підсумок:** DFS - це **пошук «у глибину» з поверненням назад**, який обходить граф, ідучи шляхом до кінця, перш ніж перейти до інших гілок.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.