Что такое DFS и для чего он используется?
2026-02-26 18:56 Diff
https://ru.hexlet.io/blog/posts/chto-takoe-dfs-i-dlya-chego-on-ispolzuetsya

Алгоритм поиска в глубину (DFS, Depth-First Search) — основа для решения множества задач, связанных с графами и деревьями. Этот алгоритм используется для обхода графа, где стратегия заключается в том, чтобы как можно глубже исследовать выбранный путь до достижения пункта назначения или конца пути. DFS применяется в разных ситуациях: для решения головоломок, навигации по сложным структурам данных или поиска в деревьях решений.

Содержание

Где используется DFS?

Поиск в глубину применяется в следующих задачах:

  • Поиск пути в лабиринте. DFS помогает найти решение в головоломках, например в лабиринтах, где нужно искать выход, двигаясь вдоль путей, пока не встретится тупик или выход из лабиринта. Еще можно его использовать для решения судоку или раскраски графа, исследуя возможные решения.
  • Топологическая сортировка. Для упорядочивания элементов с зависимостями, например при компиляции исходного кода или планировании задач, которые зависят от других.
  • Поиск циклов в графах. Определить, есть ли циклы в ориентированных и неориентированных графах.
  • Поиск сильно связных компонентов. В направленных графах DFS может быть использован для нахождения взаимосвязанных компонентов.
  • Поиск в социальной сети. С помощью DFS может обнаружить всех связанных пользователей в социальной сети, начиная с определенного пользователя. Например, алгоритм может исследовать все связи человека (друзья, друзья друзей) до определенного уровня.
  • Поиск в деревьях решений. Помогает исследовать все возможные ходы или действия, чтобы найти решение, например, в игре в шахматы.

Также полезно:

Что такое алгоритмы: простое руководство для новичков

Как работает DFS?

Алгоритм DFS основывается на концепции «погружайся глубже, головой вперед» («go deep, head first»). То есть он начинает поиск с одной вершины и движется по графу, углубляясь в определенном направлении, пока не дойдет до конца пути или тупика. Когда тупик или точка назначения найдены, алгоритм возвращается к предыдущей вершине, чтобы исследовать другие пути. Принцип работы: идти как можно глубже, прежде чем переходить к соседним узлам.

Работу DFS можно описать следующим образом:

  1. Начинаем с исходной вершины.
  2. Маркируем ее как посещенную.
  3. Рекурсивно исследуем соседей этой вершины, углубляясь в граф.
  4. После того как все соседи исследованы, возвращаемся к предыдущей вершине и продолжаем искать пути.

Когда мы говорим о «соседях», это значит, что мы исследуем все вершины, которые напрямую соединены с текущей. Например, если вершина A соединена с вершинами B и C, то соседями вершины A будут вершины B и C.

Модификации DFS

DFS имеет несколько популярных модификаций, которые помогают улучшить его эффективность в различных задачах:

  • Итеративный углубляющий обход (Iterative Deepening DFS). Эта модификация используется, чтобы избежать переполнения стека при глубоком рекурсивном обходе. Она ограничивает глубину обхода и выполняет несколько итераций с увеличением глубины.
  • Обход с ограничением по глубине. В некоторых случаях можно ограничить максимальную глубину обхода, чтобы избежать слишком долгого выполнения или чрезмерного использования памяти при работе с большими графами.
  • DFS с восстановлением пути. Этот вариант позволяет найти не только пункт назначения, но и сохранить сам путь обхода, приведший к точке назначения, что полезно в задачах, требующих исследования всех вариантов решений.

Библиотеки для работы с графами

В реальных приложениях для работы с графами и алгоритмами обхода можно использовать специализированные библиотеки:

  • NetworkX (Python). Предоставляет готовые функции для поиска в глубину, топологической сортировки и других алгоритмов графов.
  • Graphlib (JavaScript). Подходит для работы с графами в JavaScript и поддерживает различные методы обхода и алгоритмы на графах.
  • Boost Graph Library (C++). Комплексная библиотека для C++, которая предоставляет широкие возможности для работы с графами, включая поддержку алгоритмов поиска в глубину.

Рекурсивная и нерекурсивная реализация DFS

Рекурсия — это метод программирования, когда функция вызывает саму себя. В случае с DFS рекурсия позволяет удобно углубляться в граф, исследуя его вершины одну за другой, пока не дойдем до конца пути. Когда мы достигли тупика или нужной вершины, рекурсивная функция возвращается к предыдущей вершине и продолжает поиски.

Рекурсивный подход к DFS легко применяется, так как каждый вызов функции как бы углубляется в граф, пока не достигнет конечной вершины. В Python это может выглядеть так:

В этом примере граф представлен как словарь, где ключи — вершины, а значения — это множества соседей. Алгоритм начинается с вершины start_node, помечает ее как посещенную и затем рекурсивно вызывает себя для каждого непосещенного соседа.

Когда глубина графа велика, использование рекурсии может привести к переполнению стека. В таких случаях можно использовать нерекурсивную версию DFS, которая использует явный стек для хранения вершин.

Здесь используется обычный стек (список), хранящий вершины, которые необходимо посетить. Вершины добавляются в стек, а затем поочередно извлекаются, пока не будут посещены все возможные вершины.

Читайте также:

Как использовать срезы в Python: простое руководство для новичков

Визуализация DFS

Для наглядности можно использовать визуализации, чтобы показать, как работает алгоритм. Графы представляют собой узлы и ребра, и на каждом шаге алгоритма вершины графа окрашиваются, чтобы визуально отразить процесс обхода или обозначить текущее состояние каждой вершины, показывая порядок обхода.

Пример визуализации может быть создан с использованием библиотек Python, таких как matplotlib и networkx, которые помогают рисовать графы и визуализировать процесс обхода.

Связь с другими алгоритмами

DFS тесно связан с другими алгоритмами, такими как поиск в ширину (BFS) и алгоритм Дейкстры. Рассмотрим основные отличия:

  • DFS углубляется до конца пути, тогда как BFS обходит граф по уровням.
  • Дейкстра используется для нахождения кратчайшего пути во взвешенных графах, в отличие от DFS, который не учитывает веса ребер.

Заключение

DFS — это ключевой алгоритм для обхода графов, который применяется в различных задачах — от поиска решений до топологической сортировки и выявления циклов. Его модификации, такие как итеративный углубляющий поиск, расширяют область применения алгоритма и повышают его эффективность в решении сложных вычислительных задач. Если вы хотите освоить алгоритмы и научиться эффективно их применять, курсы для разработчиков школы Хекслет помогут вам глубже понять работу с графами и алгоритмами, а также освоить навыки на практике.