re:re:actable
Урок 053 минуты чтения

Как работают DFS и BFS для графа?

На этой странице
Кратко

DFS и BFS обходят граф, но в графе обязательно нужен visited, иначе можно зациклиться. DFS использует стек/рекурсию, BFS использует очередь. Сложность для adjacency list обычно O(V + E).

Вопрос

Как работают DFS и BFS для графа и зачем нужен visited?

DFS

function dfs(start: string, graph: Map<string, string[]>): string[] {
  const visited = new Set<string>()
  const result: string[] = []
 
  function visit(node: string): void {
    if (visited.has(node)) return
 
    visited.add(node)
    result.push(node)
 
    for (const next of graph.get(node) ?? []) {
      visit(next)
    }
  }
 
  visit(start)
  return result
}

BFS

function bfs(start: string, graph: Map<string, string[]>): string[] {
  const visited = new Set([start])
  const result: string[] = []
  const queue = [start]
  let head = 0
 
  while (head < queue.length) {
    const node = queue[head++]
    result.push(node)
 
    for (const next of graph.get(node) ?? []) {
      if (!visited.has(next)) {
        visited.add(next)
        queue.push(next)
      }
    }
  }
 
  return result
}

Как отличается порядок

A --- B --- D
|           |
C --------- E

Соседи: A: [B, C], B: [A, D], C: [A, E], D: [B, E], E: [C, D].

DFS из A: A, B, D, E, C   - уходит по одной дороге до упора, потом возвращается
BFS из A: A, B, C, D, E   - сначала все соседи A, потом соседи соседей

Без visited DFS пошел бы A -> B -> A -> B ... бесконечно, потому что ребро A - B ведет в обе стороны.

В BFS вершину помечают visited в момент добавления в очередь, а не при извлечении. Иначе одна вершина может попасть в очередь несколько раз - например, E добавили бы и из C, и из D.

Когда DFS?

  • connected components;
  • cycle detection;
  • topological sort;
  • backtracking;
  • path existence;
  • flood fill.

Когда BFS?

  • shortest path в unweighted graph;
  • level by level;
  • minimum number of steps;
  • nearest target;
  • word ladder-like tasks.

Что отвечать на собеседовании?

DFS идет в глубину и использует stack или recursion, BFS идет слоями и использует queue. В графах нужно множество visited, чтобы не ходить по циклам. Для adjacency list оба обхода работают за O(V + E), потому что посещают вершины и ребра.

Что важно помнить: частые ошибки

  • Не использовать visited.
  • Отмечать visited слишком поздно в BFS.
  • Использовать shift() для большой queue.
  • Путать shortest path в weighted и unweighted graph.
  • Не учитывать disconnected graph.

Мини-шпаргалка

  • DFS - stack/recursion.
  • BFS - queue.
  • Graph needs visited.
  • Time O(V + E).
  • BFS shortest path только для unweighted.
  • Disconnected graph требует запуска из всех vertices.

Документация

Wikipedia: Breadth-first search, Wikipedia: Depth-first search.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам