В чём разница между BFS и DFS при обходе графа? Когда выгоднее каждый?

Основное различие между BFS и DFS

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

Когда использовать BFS

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

Когда использовать DFS

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

Пример кода на JavaScript

// BFS
function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();
    if (visited.has(node)) continue;
    visited.add(node);
    for (const neighbor of graph[node]) {
      queue.push(neighbor);
    }
  }
  return visited;
}

// DFS (рекурсивно)
function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  for (const neighbor of graph[node]) {
    dfs(graph, neighbor, visited);
  }
  return visited;
}

Вывод

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