Как работает поиск в глубину и как его реализовать в JavaScript

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

Поиск в глубину включает следующие шаги:

  1. Во-первых, текущий узел устанавливается как посещенный. Можно использовать различные структуры данных, такие как HashMap или двумерный массив, но наиболее распространенный и простой способ сделать это — использовать одномерный массив. Это делается для того, чтобы в циклических графах узлы не посещались повторно. Если бы узлы нужно было пересматривать, то рекурсия продолжалась бы вечно.
  2. Во-вторых, проходится каждая из точек, примыкающих к текущему узлу, если они не были посещены ранее. Проверить, посещали ли они ранее, можно путем проверки структуры данных, которая хранит информацию о том, посещался ли узел или нет. Есть много способов найти, какие точки следует пройти дальше. Например, матрица смежности может быть итерирована, или, если граф имеет форму сетки, точки вокруг текущей точки могут быть идентифицированы и пройдены.

Временная сложность выполнения поиска в глубину составляет O (узлы + ребра). Временная сложность составляет O (узлы + ребра), потому что каждая вершина повторяется один раз, а каждое ребро повторяется дважды (хотя это может быть меньше в зависимости от реализации).

Согласно Brilliant.org, поиск в глубину имеет множество применений: от топологической сортировки до обнаружения циклов в графах и решения головоломок с одиночными решениями.

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

Давайте посмотрим, как этот пример может работать на образце графика:

Поиск в глубину, как и поиск в ширину, должен начинаться с одного узла. В этом случае узел будет узлом 0.

  1. Установите для Visit[0] значение true, поскольку узел 0 в настоящее время посещается.
  2. Пройдите через края. Поскольку узел 1 не был посещен, мы идем к узлу 1.
  3. Мы устанавливаем узел 1 как посещенный.
  4. Пройдите через края. Это ориентированный граф, и следующее ребро от 1 до 3, поэтому мы посещаем 3.
  5. Мы устанавливаем узел 3 как посещенный.
  6. Проходя по ребрам, мы посещаем узел 2 и узел 4
  7. Мы устанавливаем узел 2 как посещенный и перебираем ребра, проверяя, чтобы перейти к узлу 1, но не можем, так как он уже был посещен.
  8. Мы посещаем узел 4 и устанавливаем его для посещения.

Это продолжается для остальной части графика.

Чтобы реализовать это в JavaScript, вам сначала нужно определить посещаемый массив.

var visited = new Array(nodeCount).fill(false);

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

Теперь вам нужно запустить функцию в начальной точке.

dfs(0);

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

Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord . Заинтересованы в хакинге роста? Ознакомьтесь с разделом Схема.