Графовые алгоритмы (BFS, DFS, Dijkstra, MST, SCC)

Графовые алгоритмы — это фундамент computer science, применимый везде: от социальных сетей и интернет-маршрутизации до компиляторов и планирования задач. Граф — это набор вершин и рёбер; рёбра могут быть ориентированными или неориентированными, взвешенными или невзвешенными. От этих свойств зависит выбор алгоритма. Эта секция собирает «must-know» алгоритмы для собеса: два базовых обхода, четыре алгоритма кратчайших путей, топологическая сортировка, MST и SCC.

Когда применять

• BFS — кратчайший путь в невзвешенном графе или графе с весами 0/1 (через 0-1 BFS), уровни, level-order обходы.
• DFS — топологическая сортировка, поиск циклов, SCC (Tarjan/Kosaraju), мосты, точки сочленения, исчерпывающее исследование путей.
• Dijkstra — кратчайший путь от одной вершины при неотрицательных весах.
• Bellman-Ford — графы с отрицательными весами и детект отрицательных циклов.
• Floyd-Warshall — all-pairs shortest path для малых графов (V ≤ 400).
• Topological sort — DAG, dependency resolution, build systems, расписание курсов.
• MST (Kruskal/Prim) — минимальное соединение всех вершин (сети, кластеризация).
• SCC (Kosaraju/Tarjan) — анализ циклов, конденсация графа, 2-SAT.

Идея

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

Для взвешенных графов BFS не работает. Dijkstra — жадный алгоритм с min-heap, O((V+E) log V) при неотрицательных весах. Если веса могут быть отрицательными — Bellman-Ford, O(V·E). Для всех пар на малых графах — Floyd-Warshall O(V³).

Топологическая сортировка — линейный порядок вершин DAG, чтобы все рёбра шли «слева направо». Метод 1: DFS с post-order стеком. Метод 2: Kahn’s algorithm — BFS по in-degree.

MST для неориентированного связного взвешенного графа — дерево минимального веса. Kruskal: сортировка рёбер + DSU, O(E log E). Prim: как Dijkstra, но минимизируем вес ребра к дереву, O((V+E) log V).

SCC: максимальные подграфы, где из любой вершины достижима любая другая. Kosaraju: два DFS — прямой и на транспонированном графе. Tarjan: один DFS с low-link. Оба O(V + E).

Реализация: Dijkstra с Min-Heap

Задача (Network Delay Time): дан граф из n узлов, массив times[i] = [u, v, w] (ребро u→v весом w), стартовая вершина k. Найти время, за которое сигнал достигнет всех узлов; если невозможно — -1.

class MinHeap<T> {
  private heap: T[] = [];
  constructor(private compare: (a: T, b: T) => number) {}

  push(val: T): void {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown(0);
    return min;
  }

  private bubbleUp(idx: number): void {
    while (idx > 0) {
      const parent = (idx - 1) >> 1;
      if (this.compare(this.heap[idx], this.heap[parent]) < 0) {
        [this.heap[idx], this.heap[parent]] = [this.heap[parent], this.heap[idx]];
        idx = parent;
      } else break;
    }
  }

  private bubbleDown(idx: number): void {
    const len = this.heap.length;
    while (true) {
      let smallest = idx;
      const left = 2 * idx + 1;
      const right = 2 * idx + 2;
      if (left < len && this.compare(this.heap[left], this.heap[smallest]) < 0) smallest = left;
      if (right < len && this.compare(this.heap[right], this.heap[smallest]) < 0) smallest = right;
      if (smallest !== idx) {
        [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
        idx = smallest;
      } else break;
    }
  }

  get size(): number { return this.heap.length; }
}

function networkDelayTime(times: number[][], n: number, k: number): number {
  const graph: number[][][] = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) graph[u].push([v, w]);

  const dist = Array(n + 1).fill(Infinity);
  dist[k] = 0;

  const heap = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);
  heap.push([0, k]);

  while (heap.size > 0) {
    const [d, u] = heap.pop()!;
    if (d > dist[u]) continue; // ленивое удаление устаревших записей

    for (const [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        heap.push([dist[v], v]);
      }
    }
  }

  let maxDist = 0;
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1;
    maxDist = Math.max(maxDist, dist[i]);
  }
  return maxDist;
}

Трассировка для times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2

Init: dist=[∞,∞,0,∞,∞], heap=[(0,2)]
pop(0,2): обновляем dist[1]=1, dist[3]=1; heap=[(1,1),(1,3)]
pop(1,1): нет исходящих; heap=[(1,3)]
pop(1,3): dist[4]=2; heap=[(2,4)]
pop(2,4): нет исходящих; heap=[]
dist=[∞,1,0,1,2]; max=2 → ответ 2

Сложность Dijkstra

• Время: O((V + E) log V) — каждое ребро релаксируется один раз, операции с heap — O(log E ≤ 2 log V).
• Память: O(V + E) для adjacency list + O(V) для dist/heap.

Bellman-Ford

Релаксируем все рёбра V-1 раз. На V-й итерации, если можем ещё релаксировать — есть отрицательный цикл.

function bellmanFord(edges: number[][], V: number, src: number): number[] | null {
  const dist = Array(V).fill(Infinity);
  dist[src] = 0;

  for (let i = 0; i < V - 1; i++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return null; // отрицательный цикл
    }
  }
  return dist;
}

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

Floyd-Warshall

DP для all-pairs shortest paths. dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j]). Можно сжать k-измерение.

function floydWarshall(dist: number[][]): number[][] {
  const n = dist.length;
  const d = dist.map((row) => row.slice());

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (d[i][k] + d[k][j] < d[i][j]) {
          d[i][j] = d[i][k] + d[k][j];
        }
      }
    }
  }
  return d;
}

Сложность O(V³). Для V ≤ 400 практически приемлемо.

Топологическая сортировка (Kahn)

function topologicalSort(graph: number[][], V: number): number[] | null {
  const inDegree = Array(V).fill(0);
  for (let u = 0; u < V; u++) {
    for (const v of graph[u]) inDegree[v]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < V; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const result: number[] = [];
  while (queue.length) {
    const u = queue.shift()!;
    result.push(u);
    for (const v of graph[u]) {
      if (--inDegree[v] === 0) queue.push(v);
    }
  }

  return result.length === V ? result : null; // null если цикл
}

Kruskal MST

Сортируем рёбра по весу, итерируем; для каждого ребра (u, v): если в разных компонентах (DSU), добавляем в MST и объединяем. Останавливаемся, когда взяли V-1 рёбер.

class DSU {
  private parent: number[];
  private rank: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = Array(n).fill(0);
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x: number, y: number): boolean {
    const rx = this.find(x);
    const ry = this.find(y);
    if (rx === ry) return false;

    if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
    else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
    else { this.parent[ry] = rx; this.rank[rx]++; }
    return true;
  }
}

function kruskal(V: number, edges: number[][]): number {
  edges.sort((a, b) => a[2] - b[2]);
  const dsu = new DSU(V);
  let mstWeight = 0;
  let edgesUsed = 0;

  for (const [u, v, w] of edges) {
    if (dsu.union(u, v)) {
      mstWeight += w;
      if (++edgesUsed === V - 1) break;
    }
  }

  return edgesUsed === V - 1 ? mstWeight : -1;
}

Kosaraju SCC

Два DFS. Первый: обход всех вершин, post-order в стек. Второй: на транспонированном графе, обход в обратном порядке стека — каждое DFS-дерево — это SCC.

function kosaraju(graph: number[][], V: number): number[][] {
  const visited = Array(V).fill(false);
  const stack: number[] = [];

  const dfs1 = (u: number): void => {
    visited[u] = true;
    for (const v of graph[u]) if (!visited[v]) dfs1(v);
    stack.push(u);
  };

  for (let i = 0; i < V; i++) if (!visited[i]) dfs1(i);

  const transposed: number[][] = Array.from({ length: V }, () => []);
  for (let u = 0; u < V; u++) {
    for (const v of graph[u]) transposed[v].push(u);
  }

  visited.fill(false);
  const sccs: number[][] = [];

  const dfs2 = (u: number, component: number[]): void => {
    visited[u] = true;
    component.push(u);
    for (const v of transposed[u]) if (!visited[v]) dfs2(v, component);
  };

  while (stack.length) {
    const u = stack.pop()!;
    if (!visited[u]) {
      const component: number[] = [];
      dfs2(u, component);
      sccs.push(component);
    }
  }

  return sccs;
}

Сложность

Алгоритм	Время	Память
BFS / DFS	O(V + E)	O(V)
Dijkstra (heap)	O((V + E) log V)	O(V + E)
Bellman-Ford	O(V · E)	O(V)
Floyd-Warshall	O(V³)	O(V²)
Kahn’s topological	O(V + E)	O(V)
Kruskal	O(E log E)	O(V + E)
Prim (heap)	O((V + E) log V)	O(V + E)
Kosaraju / Tarjan	O(V + E)	O(V + E)

Почему Dijkstra не работает с отрицательными весами

Осторожно

Dijkstra жадно финализирует расстояние до вершины при извлечении из heap, предполагая, что это минимум. При отрицательных весах может найтись более короткий путь через ещё не обработанные вершины с отрицательным ребром — но мы уже финализировали и больше не обновим.

Контрпример: A→B вес 1, B→C вес 1, A→C вес 5, C→B вес -10. Dijkstra из A: dist[B]=1, финализируем. Потом dist[C]=2 через B. Но правильный путь A→C→B даёт dist[B] = 5 - 10 = -5! Нужен Bellman-Ford.

Типичные ошибки и подводные камни

• Забытый visited — бесконечный цикл в обходе.
• Неправильная инициализация dist: Infinity для всех, кроме старта.
• Dijkstra на отрицательных весах — даёт неправильный ответ.
• Heap без ленивого удаления — устаревшие записи дают неверный результат, либо нужен decrease-key.
• Off-by-one в индексах: 0-indexed vs 1-indexed.
• Несвязные компоненты — нужен внешний цикл по всем непосещённым.
• DAG vs циклический граф — топосорт работает только для DAG.

Edge cases: изолированные вершины, петли, мультирёбра, отрицательные циклы.

Follow-up вопросы

• В чём разница между BFS и Dijkstra? BFS — простая очередь (FIFO), невзвешенный граф, O(V+E). Dijkstra — min-heap, взвешенный граф с неотрицательными весами, O((V+E) log V). BFS — это Dijkstra для весов = 1.

• Когда использовать Bellman-Ford вместо Dijkstra? При отрицательных весах или для детекта отрицательных циклов. Медленнее (O(V·E) vs O((V+E) log V)), но корректен.

• Как определить цикл в неориентированном графе? DFS: если встретили посещённую вершину, не являющуюся родителем в DFS-дереве — цикл. Альтернатива: DSU — если union возвращает false, цикл.

• Кратчайший путь в графе с весами 0 и 1? 0-1 BFS через deque: вес 0 — push_front, вес 1 — push_back. O(V+E), быстрее Dijkstra.

• Найти мосты в графе. DFS с tin[u] (время входа) и low[u] (минимальное tin, достижимое из поддерева). Ребро (u, v) — мост, если low[v] > tin[u]. O(V + E).

• Dijkstra с лимитом k остановок? Состояние (dist, node, stops), priority queue по dist. При релаксации проверяем лимит. Альтернатива: Bellman-Ford с k+1 итерациями (LeetCode 787).

Чеклист на собес

• Сразу определи: ориентирован/нет, взвешен/нет, есть ли отрицательные веса.
• Выбирай представление: adjacency list для разреженных, matrix для плотных или V ≤ 400.
• Не забудь visited и обработку несвязных компонент.
• Для Dijkstra используй ленивое удаление — это упрощает priority queue.
• Для топосорта проверяй, что вышло V вершин, иначе цикл.
• MST: Kruskal — короче кодом (если есть DSU); Prim — если граф плотный.