Обход графа в глубину (DFS)

Идём как можно глубже по одному направлению, пока есть куда идти, потом «отматываемся назад».

Идея алгоритма

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

Сложность:

Время: O(V + E)
Память: O(V) (за счёт стека рекурсии или явного стека)

Плюсы

Очень простая рекурсивная реализация;
Подходит для поиска путей, проверки связности;
Используется в топологической сортировке, поиске циклов и др.

Минусы

Не находит кратчайший путь (по числу рёбер);
Глубокая рекурсия может привести к переполнению стека.

Пример кода

function dfs(adj, v, visited = new Set()) {
  visited.add(v);
  console.log(v);
  for (const to of adj[v] ?? []) {
    if (!visited.has(to)) {
      dfs(adj, to, visited);
    }
  }
}

Попробуй самостоятельно написать алгоритм, а затем сравнить

НазадОбход в ширину (BFS)ВпередИдея хеш-таблицы

Полезные темы

Рекомендуем изучить эти темы для лучшего понимания