Графовые алгоритмы: BFS и DFS

BFS (Breadth-First Search) и DFS (Depth-First Search) — два фундаментальных алгоритма обхода графа: BFS исследует граф «вширь» слой за слоем, DFS — «вглубь» до конца ветки перед возвратом.

Зачем нужно

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

Где используется

  • BFS: кратчайший путь в невзвешенном графе, обход дерева по уровням, поиск «на расстоянии N шагов»
  • DFS: топологическая сортировка, обнаружение циклов, поиск компонент связности (SCC)
  • Оба: веб-краулеры, поиск в лабиринте, обход дерева DOM

Основной контент

BFS — поиск в ширину

Использует очередь (FIFO). Посещает всех соседей текущего уровня до перехода на следующий.

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = ;

  while (queue.length > 0) {
    const node = queue.shift(); // O(1) с настоящей очередью
    order.push(node);

    for (const neighbor of graph[node] || ) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

// Кратчайший путь в невзвешенном графе
function shortestPath(graph, start, end) {
  const visited = new Set([start]);
  const queue = [[start, [start]]]; // [node, path]

  while (queue.length > 0) {
    const [node, path] = queue.shift();
    if (node === end) return path;
    for (const neighbor of graph[node] || ) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }
  return null;
}

DFS — поиск в глубину

Использует стек (явный или стек вызовов при рекурсии).

// Рекурсивный DFS
function dfsRecursive(graph, node, visited = new Set) {
  visited.add(node);
  console.log(node);
  for (const neighbor of graph[node] || ) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited);
    }
  }
}

// Итеративный DFS (через явный стек)
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = ;

  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    for (const neighbor of graph[node] || ) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
  return order;
}

Пример графа

const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: , E: , F: 
};

// BFS от A: A → B → C → D → E → F (по уровням)
// DFS от A: A → B → D → E → C → F (вглубь)
console.log(bfs(graph, 'A'));          // ['A', 'B', 'C', 'D', 'E', 'F']
console.log(dfsIterative(graph, 'A')); // ['A', 'C', 'F', 'B', 'E', 'D']

Сравнение BFS и DFS

Критерий BFS DFS
Структура данных Очередь Стек / рекурсия
Память O(ширина уровня) O(высота дерева)
Кратчайший путь (невзвешенный) Да Нет
Обнаружение цикла Да Да
Топологическая сортировка Нет (без модификации) Да
Сложность O(V + E) O(V + E)

Частые ошибки

  • Не использовать множество visited — граф с циклами вызовет бесконечный цикл.
  • Применять BFS для поиска кратчайшего пути во взвешенном графе — нужен алгоритм Дейкстры.
  • Путать порядок обхода в итеративном DFS: из-за стека порядок соседей реверсирован относительно рекурсивного DFS.
  • Использовать рекурсивный DFS на глубоких графах (n > 10^4) — stack overflow.

Связанные темы

Ресурсы