Какие продвинутые 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.