Поиск в глубину в JavaScript: DFS алгоритм с примерами кода

hannadev

Поиск в глубину (DFS) - это базовый алгоритм для обхода графов и деревьев в JavaScript. Он помогает исследовать структуры данных, находя пути, циклы или компоненты связности.

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

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

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

Представь граф как лабиринт: DFS идет по коридору до тупика, затем возвращается и пробует другой. В отличие от поиска в ширину, он не гарантирует кратчайший путь, но эффективен для глубокого исследования. Сложность - O(V + E), где V - вершины, E - ребра. В JavaScript это реализуется через рекурсию или стек.

Рекурсивная основа: Функция dfs(v) отмечает v как посещенную, затем для каждого соседа вызывает dfs(сосед).
Отслеживание состояний: Вершины бывают белые (непосещены), серые (в обработке), черные (обработаны) - это предотвращает зацикливание.
Дерево обхода: Формируется из ребра, ведущих к новым вершинам; обратные ребра идут к предкам.

Реализация DFS в JavaScript

В JavaScript DFS легко написать рекурсивно для графов, представленных как объект с массивами соседей. Граф хранится в виде { ‘A’: [‘B’, ‘C’], ‘B’: [‘A’, ‘D’] }. Функция использует Set для visited, чтобы проверять посещенные узлы.

Рекурсия удобна, но для больших графов может вызвать stack overflow - тогда нужен итеративный вариант со стеком. Пример: обход графа, выводящий порядок посещения. Это базовая реализация для ориентированного или неориентированного графа.

function dfs(graph, start, visited = new Set()) {
  if (visited.has(start)) return;
  visited.add(start);
  console.log(start);
  for (let neighbor of graph[start] || []) {
    dfs(graph, neighbor, visited);
  }
}

Тип реализации	Преимущества	Недостатки	Когда использовать
Рекурсивная	Простой код, читаемость	Риск переполнения стека	Малые графы, деревья
Итеративная (стек)	Нет лимита рекурсии	Больше кода	Большие графы, production
С колбэками	Гибкость, enter/leave	Сложнее отлаживать	Кастомный обход

Рекурсивная: Идеальна для обучения, работает как естественный “уйди вглубь”.
Итеративная: Используй массив как стек - push для соседей, pop для обработки.
С состояниями: Добавь tin/tout для времени входа/выхода - полезно для мостов или SCC.

Применение DFS в реальных задачах

DFS находит мосты в графе: ребро - мост, если удаление увеличивает компоненты. Запускаем DFS, вычисляем глубину h(u) и низшую точку f(u). Если f(v) > h(u) для ребра u-v - это мост. В JS это решает задачи сетевой топологии или оптимизации.

Еще DFS обнаруживает циклы: если сосед уже в обработке (серый), то цикл есть. Применяется в проверке DAG или раскраске графа. В веб-приложениях - для сериализации компонентов или поиска путей в React-дереве.

function findCycles(graph, start, visited = new Set(), recStack = new Set()) {
  visited.add(start);
  recStack.add(start);
  for (let neighbor of graph[start] || []) {
    if (!visited.has(neighbor)) {
      if (findCycles(graph, neighbor, visited, recStack)) return true;
    } else if (recStack.has(neighbor)) {
      return true; // Цикл!
    }
  }
  recStack.delete(start);
  return false;
}

Поиск мостов: Вычисляй min(f[v], h[предок]) для backtracking.
Циклы в графе: Отслеживай recStack - серые вершины.
Компоненты связности: Запускай DFS с каждой непосещенной вершины.

Задача	Почему DFS	Альтернатива
Мосты/артикуляции	Один проход O(n)	BFS медленнее
Обнаружение циклов	Простая рекурсия	Union-Find для unions
Топосорт	Линейный порядок	Kahn’s BFS

Вариации и оптимизации DFS

Для не связанных графов запускай DFS с каждой вершины - найдешь все компоненты. В дереве DFS строит эйлеров обход. Оптимизация: используй BitSet вместо Set для скорости на больших данных.

В JS для DOM: window.document.createTreeWalker с фильтром - встроенный DFS. Для игр - генерация лабиринтов: рекурсивный backtracking. Подумай о таймерах для асинхронного DFS в браузере.

Асинхронный DFS: Используй async/await с очередью для UI не блокируй.
Bit manipulation: Для sparse графов - биты вместо Set.
С весами: Комбинируй с memoization для shortest path в DAG.

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

Ключевые метрики алгоритма

DFS создает дерево обхода с back-edges. Метрики tin/v - время входа/выхода помогают в анализе. Для мостов: f[u] = min(f[u], f[v]), проверка f[v] > h[u].

В коде отслеживай parent, чтобы различать tree/back edges. Это основа для Tarjan’s SCC или Kosaraju. Практика: реализуй на LeetCode (Number of Islands).

let time = 0;
function dfsWithTime(graph, u, parent, h, f, visited) {
  visited[u] = true;
  h[u] = time++;
  f[u] = h[u];
  for (let v of graph[u]) {
    if (v === parent) continue;
    if (!visited[v]) {
      dfsWithTime(graph, v, u, h, f, visited);
      f[u] = Math.min(f[u], f[v]);
    } else {
      f[u] = Math.min(f[u], h[v]);
    }
  }
}

По ту сторону стека рекурсии

DFS хорош для глубоких структур, но рекурсия ограничена в Node.js (~10k вызовов). Итеративный вариант с while и стеком решает проблему. Остается вопрос: как масштабировать на миллионы вершин?

Подумай о параллельном DFS или комбинации с BFS для hybrid поиска. В JS для больших данных смотри Web Workers. Это база, дальше - твои эксперименты с графами.