Поиск в глубину (Depth-First Search) в JavaScript
Как работает поиск в глубину и как его реализовать в
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.
