Поиск в глубину (DFS)

Алгоритм обхода графа, который идет вглубь насколько возможно по каждой ветке перед возвратом.

Сложность

Временная сложность: O(V + E)

Пространственная сложность: O(V)

Реализация

function dfs(graph, start) {
  const visited = new Set();
  const result = [];
  
  function explore(vertex) {
    visited.add(vertex);
    result.push(vertex);
    
    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        explore(neighbor);
      }
    }
  }
  
  explore(start);
  return result;
}

Объяснение

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

Примеры

Ввод: graph = {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: []}, start = 1

Вывод: [1, 2, 4, 5, 3, 6]