Какая структура данных подходит для эффективного обхода графа в глубину (DFS) — рекурсия или стек, и почему?

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

Почему стек

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

• Рекурсия использует стек вызовов языка — это тот же стек, только управляемый рантаймом.
• Итеративный DFS хранит стек явно в переменной.
• Очередь (FIFO) дала бы BFS, а не DFS.

Рекурсивный вариант

function dfs(node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  console.log(node);
  for (const next of node.neighbors) {
    dfs(next, visited);
  }
}

Итеративный вариант со стеком

function dfsIterative(start) {
  const stack = [start];
  const visited = new Set();
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    console.log(node);
    for (const next of node.neighbors) stack.push(next);
  }
}

Когда что выбирать

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

Итог: DFS опирается на стек как на базовую структуру данных; рекурсия — это лишь удобная форма записи того же стека. Для продакшена на больших графах предпочтительнее итеративный вариант с явным стеком.