Skip to main content

Що робить обхід у глибину (DFS)?

Структури данихJunior~1 хв читання
Запропонувати правку

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

Ідея

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

Покроково (рекурсивна версія)

  1. Почати зі стартової вершини і позначити її як відвідану.
  2. Для кожного сусіда цієї вершини:
  • Якщо сусід не відвіданий, запустити DFS для нього.
  1. Продовжувати, поки не обійдемо всі досяжні вершини.

Приклад

Для графа

javascript
A - B - C | | D - E

Якщо почати з A, можливий порядок обходу: A → B → C → E → D

(Точний порядок залежить від порядку сусідів у структурі даних.)

Реалізація

  • Використовує стек (Stack), неявно через рекурсію або явно через структуру даних.

Застосування

  • Перевірка зв'язності графа.
  • Пошук циклів.
  • Топологічне сортування (в орієнтованих графах).
  • Пошук шляхів, компонент зв'язності, «островів» тощо.

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

Коротка відповідь

Для співбесіди
Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Запропонувати правку