Графы (Graphs)
1. Способы представления графа
Adjacency List (Список смежности)
Самый частый формат. Объект или массив, где ключ — узел, значение — массив соседей.
// Graph: 0 -> 1, 0 -> 2, 2 -> 3
const graph = {
0: [1, 2],
1: [],
2: [3],
3: []
};Adjacency Matrix (Матрица смежности)
Двумерный массив. grid[i][j] === 1 значит есть ребро. Чаще используется в задачах-лабиринтах (Grid).
const grid = [
[0, 1, 0],
[1, 0, 1],
[0, 1, 0]
];2. Базовые обходы (Traversal)
В отличие от деревьев, в графах обязательно нужен visited (Set или массив), чтобы не зациклиться.
DFS (Глубина) — Рекурсивно
Когда: Поиск пути, проверка циклов, компоненты связности.
function dfs(node, visited = new Set()) {
if (visited.has(node)) return;
visited.add(node);
console.log(node); // Обработка
for (const neighbor of graph[node]) {
dfs(neighbor, visited);
}
}BFS (Ширина) — Очередь
Когда: Кратчайший путь в невзвешенном графе, “круги на воде”.
function bfs(startNode) {
const queue = [startNode];
const visited = new Set([startNode]);
while (queue.length > 0) {
const node = queue.shift();
console.log(node); // Обработка
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}3. Матричные задачи (Grid DFS/BFS)
Граф задан неявно как сетка. Соседи — это клетки сверху, снизу, слева, справа.
Шаблон DFS для сетки (Number of Islands)
var numIslands = function(grid) {
if (!grid || grid.length === 0) return 0;
const rows = grid.length;
const cols = grid[0].length;
let count = 0;
function dfs(r, c) {
// Проверка границ и "воды"
if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') {
return;
}
// Помечаем как посещенное (топим остров)
grid[r][c] = '0';
// Идем в 4 стороны
dfs(r + 1, c);
dfs(r - 1, c);
dfs(r, c + 1);
dfs(r, c - 1);
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
count++;
dfs(r, c);
}
}
}
return count;
};- 🟡 200. Number of Islands
- 🟡 695. Max Area of Island
- 🟢 733. Flood Fill
- 🟡 994. Rotting Oranges (тут нужен BFS!)
4. Union Find (Disjoint Set Union - DSU)
Когда: Связность компонентов, поиск цикла в ненаправленном графе, объединение множеств. Очень эффективен (почти O(1)).
Шаблон класса DSU
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = new Array(n).fill(1); // или size
}
find(x) {
if (this.parent[x] !== x) {
// Path compression (сжатие путей)
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
// Union by rank (присоединяем меньшее к большему)
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
return true; // Успешно объединили
}
return false; // Уже были в одном множестве (цикл?)
}
}- 🟡 547. Number of Provinces
- 🟡 684. Redundant Connection (поиск цикла)
- 🟡 323. Number of Connected Components in an Undirected Graph (Premium)
5. Topological Sort (Kahn’s Algorithm)
Когда: Зависимости задач (курсы, сборка билда), Directed Acyclic Graph (DAG). Идея: Считаем входящие связи (indegree). Начинаем с тех, у кого 0 входящих.
var canFinish = function(numCourses, prerequisites) {
const graph = Array.from({length: numCourses}, () => []);
const indegree = new Array(numCourses).fill(0);
// 1. Строим граф и indegree
for (const [course, pre] of prerequisites) {
graph[pre].push(course);
indegree[course]++;
}
// 2. Queue c "независимыми" узлами (0 входящих)
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) queue.push(i);
}
let count = 0;
while (queue.length > 0) {
const node = queue.shift();
count++;
for (const neighbor of graph[node]) {
indegree[neighbor]--;
if (indegree[neighbor] === 0) {
queue.push(neighbor);
}
}
}
return count === numCourses; // Если посетили все, значит циклов нет
};- 🟡 207. Course Schedule
- 🟡 210. Course Schedule II (вернуть порядок)
6. Shortest Path (Dijkstra) - Взвешенный граф
Когда: Найти кратчайший путь в графе с неотрицательными весами. Нужен: MinPriorityQueue (в JS нет встроенной, на собеседовании можно эмулировать массивом с sort, но это медленнее O(n log n) vs O(e log v)).
Шаблон (с простым массивом для простоты понимания)
function dijkstra(n, edges, start) {
const graph = {}; // build graph...
const distances = new Array(n).fill(Infinity);
distances[start] = 0;
// [distance, node]
const pq = [[0, start]];
while (pq.length > 0) {
// Эмуляция MinPQ: сортируем и берем минимум
pq.sort((a, b) => a[0] - b[0]);
const [dist, node] = pq.shift();
if (dist > distances[node]) continue;
if (graph[node]) {
for (const [neighbor, weight] of graph[node]) {
const newDist = dist + weight;
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
pq.push([newDist, neighbor]);
}
}
}
}
return distances;
}- 🟡 743. Network Delay Time
- 🟡 787. Cheapest Flights Within K Stops (тут BFS или Bellman-Ford лучше)
7. Clone Graph
Когда: Нужно сделать глубокую копию графа. Используем Map для маппинга OldNode -> NewNode.
var cloneGraph = function(node) {
if (!node) return null;
const map = new Map();
function dfs(curr) {
if (map.has(curr)) return map.get(curr);
const copy = new Node(curr.val);
map.set(curr, copy);
for (const neighbor of curr.neighbors) {
copy.neighbors.push(dfs(neighbor));
}
return copy;
}
return dfs(node);
};Мини-шпаргалка: какой паттерн выбрать?
| Задача | Паттерн | Ключ |
|---|---|---|
| Поиск пути A -> B (любого) | DFS | Простой, рекурсивный |
| Кратчайший путь (вес = 1) | BFS | Уровни, queue |
| Кратчайший путь (вес > 0) | Dijkstra | PriorityQueue |
| Острова, лабиринты (сетка) | Grid DFS/BFS | Directions array [[0,1]...] |
| Связность, объединение | Union Find | Find root, Union ranks |
| Цикл в directed графе | Topological Sort (Kahn) | Indegree array |
| Зависимости (порядок задач) | Topological Sort | Indegree = 0 в очередь |
| Цикл в undirected графе | Union Find или DFS | Если встретили visited != parent |