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

Какие продвинутые graph algorithms стоит знать?

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

После BFS, DFS, Dijkstra и topological sort полезно знать обзорно еще несколько graph algorithms: cycle detection, connected components, bipartite check, Bellman-Ford, Floyd-Warshall, minimum spanning tree и strongly connected components.

Вопрос

Какие продвинутые алгоритмы на графах стоит знать после базовых BFS/DFS?

Что уже нужно знать до этого

Перед этим материалом желательно понимать:

  • что такое graph;
  • adjacency list;
  • DFS;
  • BFS;
  • visited;
  • weighted/unweighted graph;
  • directed/undirected graph;
  • topological sort;
  • Dijkstra.

Cycle detection

Undirected graph

В undirected graph цикл можно искать через DFS с parent.

function hasCycleUndirected(graph: Map<number, number[]>): boolean {
  const visited = new Set<number>()
 
  function dfs(node: number, parent: number): boolean {
    visited.add(node)
 
    for (const next of graph.get(node) ?? []) {
      if (!visited.has(next)) {
        if (dfs(next, node)) return true
      } else if (next !== parent) {
        return true
      }
    }
 
    return false
  }
 
  for (const node of graph.keys()) {
    if (!visited.has(node) && dfs(node, -1)) {
      return true
    }
  }
 
  return false
}

Идея: если пришли в уже посещенную вершину, которая не является родителем, есть цикл.

Directed graph

В directed graph используют цвета:

0 = unvisited
1 = visiting
2 = done

Если DFS попал в visiting, найден цикл.

function hasCycleDirected(graph: Map<string, string[]>): boolean {
  const state = new Map<string, 0 | 1 | 2>() // по умолчанию 0
 
  function dfs(node: string): boolean {
    state.set(node, 1) // visiting: вершина на текущем пути
 
    for (const next of graph.get(node) ?? []) {
      const s = state.get(next) ?? 0
      if (s === 1) return true // вернулись в вершину текущего пути - цикл
      if (s === 0 && dfs(next)) return true
    }
 
    state.set(node, 2) // done: все пути из вершины проверены
    return false
  }
 
  for (const node of graph.keys()) {
    if ((state.get(node) ?? 0) === 0 && dfs(node)) return true
  }
 
  return false
}

Почему недостаточно одного visited, как в undirected graph? В графе A -> B, A -> C, C -> B вершина B будет посещена дважды, но цикла нет: второй раз мы пришли в нее по другому пути, а не вернулись по кругу. Цикл - это только возврат в вершину, которая сейчас на пути (visiting).

Connected components

Connected components - группы вершин, достижимых друг из друга.

function countComponents(graph: Map<number, number[]>): number {
  const visited = new Set<number>()
  let components = 0
 
  function dfs(node: number): void {
    visited.add(node)
 
    for (const next of graph.get(node) ?? []) {
      if (!visited.has(next)) {
        dfs(next)
      }
    }
  }
 
  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      components++
      dfs(node)
    }
  }
 
  return components
}

Альтернатива: DSU.

Bipartite graph

Bipartite graph можно раскрасить в два цвета так, чтобы соседние вершины имели разные цвета.

function isBipartite(graph: number[][]): boolean {
  const color = new Array(graph.length).fill(-1)
 
  for (let start = 0; start < graph.length; start++) {
    if (color[start] !== -1) continue
 
    const queue = [start]
    let head = 0
    color[start] = 0
 
    while (head < queue.length) {
      const node = queue[head++]
 
      for (const next of graph[node]) {
        if (color[next] === -1) {
          color[next] = 1 - color[node]
          queue.push(next)
        } else if (color[next] === color[node]) {
          return false
        }
      }
    }
  }
 
  return true
}

Где встречается:

  • разделение на две группы;
  • проверка conflicts;
  • possible bipartition.

Bellman-Ford

Bellman-Ford ищет shortest path от одной вершины и работает с отрицательными ребрами.

Ограничения:

  • работает медленнее Dijkstra;
  • может обнаружить negative cycle.

Идея:

повторить V - 1 раз:
  пройти по всем ребрам и расслабить каждое
type WeightedEdge = [from: number, to: number, weight: number]
 
function bellmanFord(n: number, edges: WeightedEdge[], start: number): number[] | null {
  const dist = new Array(n).fill(Infinity)
  dist[start] = 0
 
  for (let i = 0; i < n - 1; i++) {
    for (const [from, to, weight] of edges) {
      if (dist[from] + weight < dist[to]) dist[to] = dist[from] + weight
    }
  }
 
  // Если что-то еще улучшается, есть отрицательный цикл.
  for (const [from, to, weight] of edges) {
    if (dist[from] + weight < dist[to]) return null
  }
 
  return dist
}

Почему V - 1 раз: кратчайший путь без циклов содержит не больше V - 1 ребер, а каждый проход гарантированно "дотягивает" правильную дистанцию еще на одно ребро.

Сложность:

O(V * E)

Когда нужен:

  • есть отрицательные веса;
  • нужно обнаружить negative cycle;
  • Dijkstra нельзя применять.

Floyd-Warshall

Floyd-Warshall ищет shortest paths между всеми парами вершин.

Идея:

dist[i][j] = можно ли улучшить путь i -> j через k?
function floydWarshall(dist: number[][]): number[][] {
  const n = dist.length
  const d = dist.map((row) => [...row]) // Infinity, если ребра нет; 0 на диагонали
 
  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
}

Важно, что внешний цикл - по промежуточной вершине k.

Сложность:

O(V^3)

Когда нужен:

  • вершин мало;
  • нужны расстояния между всеми парами;
  • graph dense;
  • удобно хранить matrix.

Minimum Spanning Tree

MST - minimum spanning tree, минимальное остовное дерево.

Нужно для undirected weighted connected graph:

соединить все вершины с минимальной суммой ребер

Алгоритмы:

  • Kruskal - сортирует ребра и использует DSU;
  • Prim - растит дерево через priority queue.

Kruskal идея:

1. Отсортировать ребра по весу.
2. Идти от легких к тяжелым.
3. Добавлять ребро, если оно соединяет разные компоненты.
4. DSU помогает проверить компоненты.

Сложность:

O(E log E)

Strongly Connected Components

SCC - strongly connected components в directed graph.

Внутри SCC каждая вершина достижима из каждой другой.

Алгоритмы:

  • Kosaraju;
  • Tarjan.

На обычных frontend/backend собеседованиях SCC спрашивают реже, чем BFS/DFS/Dijkstra/topological sort, но полезно знать название и идею.

Что учить глубоко, а что обзорно

Глубоко:

  • BFS/DFS;
  • graph representation;
  • connected components;
  • cycle detection;
  • topological sort;
  • Dijkstra.

Уверенно обзорно:

  • DSU;
  • bipartite check;
  • Bellman-Ford;
  • Floyd-Warshall;
  • Kruskal/Prim;
  • SCC.

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

  • Применять Dijkstra при отрицательных весах.
  • Путать MST и shortest path.
  • Использовать topological sort на graph с cycle.
  • Искать cycle в directed graph так же, как в undirected.
  • Забывать проходить все компоненты, если graph disconnected.
  • Использовать adjacency matrix для sparse graph без причины.

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

После BFS/DFS важно знать, что cycle detection зависит от типа графа: в undirected graph учитывают parent, в directed graph используют цвета или recursion stack. Для connected components подходит DFS/BFS или DSU. Для shortest path: BFS для unweighted, Dijkstra для неотрицательных весов, Bellman-Ford для отрицательных ребер, Floyd-Warshall для all-pairs на небольших графах. MST решается Kruskal с DSU или Prim с priority queue.

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

  • Undirected cycle -> DFS + parent или DSU.
  • Directed cycle -> colors/recursion stack.
  • Components -> DFS/BFS/DSU.
  • Bipartite -> 2-color BFS/DFS.
  • Negative edges -> Bellman-Ford.
  • All-pairs shortest path -> Floyd-Warshall.
  • MST -> Kruskal/Prim.
  • SCC -> Kosaraju/Tarjan.

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

cp-algorithms: Graph algorithms.

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

Поиск

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