Граф — это структура данных, которая представляет связи между объектами. Граф состоит из вершин (узлов) и рёбер (связей между ними).
Графы используются повсеместно:
Социальные сети: пользователи — вершины, дружба — рёбра
Маршрутизация: города — вершины, дороги — рёбра
Рекомендации: товары связаны по схожести
Анализ зависимостей: модули в проекте, задачи с приоритетами
Поиск кратчайшего пути: навигация, логистика
Паутина интернета: веб-страницы и ссылки между ними
Типы графов
Ориентированный граф — рёбра имеют направление (A → B). Неориентированный граф — рёбра двусторонние (A B). Взвешенный граф — рёбра имеют вес/стоимость. Невзвешенный граф — все рёбра одинакового веса.
Представление графа в коде
Существует три основных способа представить граф. Выбор зависит от задачи, количества вершин и плотности графа.
1. Список смежности (Adjacency List) — самый эффективный
Для каждой вершины храним список её соседей. Это самый популярный способ.
// Неориентированный граф с помощью Map
const graph = new Map();
// Добавление рёбер
graph.set('A', ['B', 'C']);
graph.set('B', ['A', 'D']);
graph.set('C', ['A', 'D']);
graph.set('D', ['B', 'C']);
// Или с помощью объекта
const graphObj = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
};
Преимущества: компактный для разреженных графов, быстрый доступ к соседям, O(V+E) память.
Недостатки: проверка наличия конкретного ребра требует линейного поиска.
2. Матрица смежности (Adjacency Matrix)
Двумерный массив, где matrix[i][j] = 1, если есть ребро между вершиной i и j.
// Граф с 4 вершинами
const matrix = [
[0, 1, 1, 0], // A: связана с B, C
[1, 0, 0, 1], // B: связана с A, D
[1, 0, 0, 1], // C: связана с A, D
[0, 1, 1, 0] // D: связана с B, C
];
// Или с индексами для удобства
const vertices = ['A', 'B', 'C', 'D'];
// Проверка ребра A → B: matrix[0][1] === 1
// Для взвешенного графа: matrix[i][j] = вес
Преимущества: быстрая проверка ребра O(1), подходит для плотных графов.
Недостатки: требует O(V²) памяти, неэффективна для разреженных графов.
3. Список рёбер (Edge List)
Просто список всех рёбер в виде пар вершин.
const edges = [
['A', 'B'],
['A', 'C'],
['B', 'D'],
['C', 'D']
];
// Для взвешенного графа:
const weightedEdges = [
['A', 'B', 5],
['A', 'C', 3],
['B', 'D', 2],
['C', 'D', 7]
];
Используется: когда нужно обрабатывать все рёбра, в алгоритмах вроде Краскала.
Класс Graph для удобства
Создадим удобный класс для работы с графами:
class Graph {
constructor(isDirected = false) {
this.adjacencyList = new Map();
this.isDirected = isDirected;
}
addVertex(vertex) {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, []);
}
}
addEdge(vertex1, vertex2, weight = 1) {
this.addVertex(vertex1);
this.addVertex(vertex2);
this.adjacencyList.get(vertex1).push({ node: vertex2, weight });
// Для неориентированного графа добавляем обратное ребро
if (!this.isDirected) {
this.adjacencyList.get(vertex2).push({ node: vertex1, weight });
}
}
getNeighbors(vertex) {
return this.adjacencyList.get(vertex) || [];
}
hasVertex(vertex) {
return this.adjacencyList.has(vertex);
}
display() {
for (let [vertex, neighbors] of this.adjacencyList) {
console.log(`${vertex} →`, neighbors.map(n => n.node).join(', '));
}
}
}
Использование:
const g = new Graph(false); // неориентированный граф
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.display();
// Вывод:
// A → B, C
// B → A, D
// C → A
// D → B
DFS (Depth-First Search) — Поиск в глубину
Как работает DFS
Начинаем с начальной вершины
Идём в глубину, посещая первого соседа
Затем идём в соседа этого соседа и т.д.
Когда соседей нет, возвращаемся (backtrack) к последней вершине и ищем другой путь
Повторяем, пока не посетим все вершины
Аналогия: исследование лабиринта — идёшь в одну сторону полностью, потом разворачиваешься и пробуешь другую.
DFS рекурсивная реализация
class Graph {
// ... предыдущий код ...
dfsRecursive(startVertex, visited = new Set(), result = []) {
visited.add(startVertex);
result.push(startVertex);
const neighbors = this.getNeighbors(startVertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
this.dfsRecursive(neighbor.node, visited, result);
}
}
return result;
}
dfs(startVertex) {
return this.dfsRecursive(startVertex);
}
}
Пример использования:
const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'D');
g.addEdge('D', 'E');
console.log(g.dfs('A')); // ['A', 'B', 'D', 'C', 'E']
Как это работает step-by-step:
Посетить A, добавить в результат
A имеет соседей B и C, идём к B (первому)
B имеет соседей A (уже посещена) и D, идём к D
D имеет соседей B (уже посещена), C и E, идём к C
C имеет соседей A (уже посещена) и D (уже посещена)
Возвращаемся к D, идём к E
E соседей нет, всё готово
DFS итеративная реализация (со стеком)
class Graph {
dfsIterative(startVertex) {
const visited = new Set();
const stack = [startVertex];
const result = [];
while (stack.length > 0) {
const vertex = stack.pop();
if (!visited.has(vertex)) {
visited.add(vertex);
result.push(vertex);
const neighbors = this.getNeighbors(vertex);
// Добавляем соседей в стек в обратном порядке
// чтобы первого соседа обработать первым
for (let i = neighbors.length - 1; i >= 0; i--) {
if (!visited.has(neighbors[i].node)) {
stack.push(neighbors[i].node);
}
}
}
}
return result;
}
}
Когда использовать DFS:
Поиск пути в лабиринте или графе
Обнаружение циклов в графе
Топологическая сортировка
Проверка связности компонент
Задачи с backtracking (судоку, головоломки)
Когда граф очень широкий (много соседей) — DFS экономит память
BFS (Breadth-First Search) — Поиск в ширину
Как работает BFS
Начинаем с начальной вершины
Посещаем всех её соседей (уровень 1)
Затем посещаем всех соседей уровня 1 (уровень 2)
Затем уровень 3 и т.д.
Продолжаем, пока не посетим все вершины
Аналогия: расширяющиеся волны в воде — сначала ближайшие точки, потом дальше.
BFS реализация (с очередью)
class Graph {
bfs(startVertex) {
const visited = new Set();
const queue = [startVertex];
const result = [];
visited.add(startVertex);
while (queue.length > 0) {
const vertex = queue.shift(); // берём первый элемент
result.push(vertex);
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
visited.add(neighbor.node);
queue.push(neighbor.node); // добавляем в конец
}
}
}
return result;
}
}
Пример использования:
const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'D');
g.addEdge('D', 'E');
console.log(g.bfs('A')); // ['A', 'B', 'C', 'D', 'E']
Как это работает step-by-step:
Очередь: [A], посетить A, результат: [A]
Соседи A: B, C. Очередь: [B, C], посетить B, результат: [A, B]
Соседи B: A (уже), D. Очередь: [C, D], посетить C, результат: [A, B, C]
Соседи A (уже), D (уже в очереди). Очередь: [D], посетить D, результат: [A, B, C, D]
Соседи B (уже), C (уже), E. Очередь: [E], посетить E, результат: [A, B, C, D, E]
Когда использовать BFS:
Поиск кратчайшего пути в невзвешенном графе
Проверка, является ли граф двудольным
Уровневый обход дерева/графа
Поиск всех вершин на определённом расстоянии
Когда граф глубокий, а решение близко к началу
DFS vs BFS
Параметр
DFS
BFS
Структура данных
Стек (рекурсия)
Очередь
Память
O(h) где h — глубина
O(w) где w — ширина
Кратчайший путь
Не гарантирует
✓ Гарантирует (невзвешённый граф)
Порядок посещения
Глубоко в одну ветку
Слой за слоем
Применение
Циклы, топосорт, backtracking
Кратчайший путь, проверка расстояния
Сложность
O(V + E)
O(V + E)
Практические примеры
Пример 1: Поиск пути между двумя вершинами
class Graph {
// ... предыдущий код ...
findPath(start, end) {
const visited = new Set();
const path = [];
const dfs = (vertex) => {
visited.add(vertex);
path.push(vertex);
if (vertex === end) {
return true; // путь найден
}
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
if (dfs(neighbor.node)) {
return true;
}
}
}
path.pop(); // backtrack
return false;
};
if (dfs(start)) {
return path;
}
return null; // пути нет
}
}
// Использование
const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('B', 'C');
g.addEdge('A', 'D');
g.addEdge('D', 'C');
console.log(g.findPath('A', 'C')); // ['A', 'B', 'C']
Пример 2: Поиск кратчайшего пути (невзвешённый граф)
class Graph {
// ... предыдущий код ...
shortestPath(start, end) {
const visited = new Set();
const queue = [[start, [start]]]; // [вершина, путь до неё]
visited.add(start);
while (queue.length > 0) {
const [vertex, path] = queue.shift();
if (vertex === end) {
return path;
}
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
visited.add(neighbor.node);
queue.push([neighbor.node, [...path, neighbor.node]]);
}
}
}
return null; // пути нет
}
}
// Использование
const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('B', 'C');
g.addEdge('A', 'D');
g.addEdge('D', 'E');
g.addEdge('E', 'C');
console.log(g.shortestPath('A', 'C')); // ['A', 'B', 'C'] (длина 2)
// Не выберет ['A', 'D', 'E', 'C'] (длина 3)
Пример 3: Проверка наличия цикла в графе
class Graph {
// ... предыдущий код ...
hasCycle() {
const visited = new Set();
const recursionStack = new Set();
const dfs = (vertex, parent = null) => {
visited.add(vertex);
recursionStack.add(vertex);
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
const nextVertex = neighbor.node;
// Для неориентированного графа проверяем, не родитель ли это
if (this.isDirected && visited.has(nextVertex) && recursionStack.has(nextVertex)) {
return true; // цикл найден
}
if (!this.isDirected && nextVertex === parent) {
continue; // пропускаем обратную ссылку
}
if (!visited.has(nextVertex)) {
if (dfs(nextVertex, vertex)) {
return true;
}
}
}
recursionStack.delete(vertex);
return false;
};
for (let vertex of this.adjacencyList.keys()) {
if (!visited.has(vertex)) {
if (dfs(vertex)) {
return true;
}
}
}
return false;
}
}
// Использование
const g1 = new Graph(false);
g1.addEdge('A', 'B');
g1.addEdge('B', 'C');
g1.addEdge('C', 'A'); // цикл!
console.log(g1.hasCycle()); // true
const g2 = new Graph(false);
g2.addEdge('A', 'B');
g2.addEdge('B', 'C');
console.log(g2.hasCycle()); // false
Пример 4: Подсчёт количества связных компонент
class Graph {
// ... предыдущий код ...
countConnectedComponents() {
const visited = new Set();
let count = 0;
const dfs = (vertex) => {
visited.add(vertex);
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
dfs(neighbor.node);
}
}
};
for (let vertex of this.adjacencyList.keys()) {
if (!visited.has(vertex)) {
dfs(vertex);
count++;
}
}
return count;
}
}
// Использование
const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('C', 'D');
g.addEdge('E', 'F');
g.addEdge('F', 'G');
console.log(g.countConnectedComponents()); // 3 компоненты: [A,B], [C,D], [E,F,G]
Пример 5: Поиск всех вершин на определённом расстоянии
class Graph {
// ... предыдущий код ...
verticesAtDistance(start, distance) {
const visited = new Set();
const queue = [[start, 0]]; // [вершина, расстояние]
const result = [];
visited.add(start);
while (queue.length > 0) {
const [vertex, dist] = queue.shift();
if (dist === distance) {
result.push(vertex);
}
if (dist < distance) {
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
visited.add(neighbor.node);
queue.push([neighbor.node, dist + 1]);
}
}
}
}
return result;
}
}
// Использование
const g = new Graph(false);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'E');
g.addEdge('D', 'F');
console.log(g.verticesAtDistance('A', 0)); // ['A']
console.log(g.verticesAtDistance('A', 1)); // ['B', 'C']
console.log(g.verticesAtDistance('A', 2)); // ['D', 'E']
console.log(g.verticesAtDistance('A', 3)); // ['F']
Пример 6: Топологическая сортировка (для ориентированного ацикличного графа)
class Graph {
// ... предыдущий код ...
topologicalSort() {
const visited = new Set();
const stack = [];
const dfs = (vertex) => {
visited.add(vertex);
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
dfs(neighbor.node);
}
}
stack.push(vertex);
};
for (let vertex of this.adjacencyList.keys()) {
if (!visited.has(vertex)) {
dfs(vertex);
}
}
return stack.reverse();
}
}
// Использование: расписание задач с зависимостями
// Задача B зависит от A, задача D зависит от B и C
const g = new Graph(true);
g.addEdge('A', 'B');
g.addEdge('B', 'D');
g.addEdge('C', 'D');
console.log(g.topologicalSort()); // ['A', 'C', 'B', 'D'] или ['C', 'A', 'B', 'D']
// Суть: A и C выполняются первыми, потом B, потом D
Пример 7: Реальный пример — поиск маршрута между аэропортами
class Graph {
// ... весь предыдущий код ...
}
// Создаём граф аэропортов
const airports = new Graph(false);
airports.addEdge('JFK', 'LAX');
airports.addEdge('JFK', 'ATL');
airports.addEdge('LAX', 'SFO');
airports.addEdge('ATL', 'DFW');
airports.addEdge('DFW', 'SFO');
airports.addEdge('ATL', 'MIA');
// Найти кратчайший маршрут из JFK в SFO
const route = airports.shortestPath('JFK', 'SFO');
console.log(`Маршрут из JFK в SFO: ${route.join(' → ')}`);
// Маршрут из JFK в SFO: JFK → LAX → SFO (2 перелёта)
// Альтернатива была бы: JFK → ATL → DFW → SFO (3 перелёта)
// Проверить, есть ли прямой путь
const allNeighbors = airports.bfs('JFK');
console.log(`Достижимые из JFK:`, allNeighbors);
// Достижимые из JFK: ['JFK', 'LAX', 'ATL', 'SFO', 'DFW', 'MIA']
Сложность алгоритмов
Временная сложность обоих алгоритмов: O(V + E)
V — количество вершин
E — количество рёбер
Мы посещаем каждую вершину один раз и рассматриваем каждое ребро один раз
Пространственная сложность:
DFS: O(h) где h — глубина графа (из-за рекурсивного стека вызовов)
BFS: O(w) где w — максимальная ширина на каждом уровне
Практический вывод: для широких графов DFS более экономен по памяти, для глубоких графов BFS.
Полный рабочий класс Graph
class Graph {
constructor(isDirected = false) {
this.adjacencyList = new Map();
this.isDirected = isDirected;
}
addVertex(vertex) {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, []);
}
}
addEdge(vertex1, vertex2, weight = 1) {
this.addVertex(vertex1);
this.addVertex(vertex2);
this.adjacencyList.get(vertex1).push({ node: vertex2, weight });
if (!this.isDirected) {
this.adjacencyList.get(vertex2).push({ node: vertex1, weight });
}
}
getNeighbors(vertex) {
return this.adjacencyList.get(vertex) || [];
}
hasVertex(vertex) {
return this.adjacencyList.has(vertex);
}
dfs(startVertex) {
const visited = new Set();
const result = [];
const dfsHelper = (vertex) => {
visited.add(vertex);
result.push(vertex);
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
dfsHelper(neighbor.node);
}
}
};
dfsHelper(startVertex);
return result;
}
bfs(startVertex) {
const visited = new Set();
const queue = [startVertex];
const result = [];
visited.add(startVertex);
while (queue.length > 0) {
const vertex = queue.shift();
result.push(vertex);
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
visited.add(neighbor.node);
queue.push(neighbor.node);
}
}
}
return result;
}
shortestPath(start, end) {
const visited = new Set();
const queue = [[start, [start]]];
visited.add(start);
while (queue.length > 0) {
const [vertex, path] = queue.shift();
if (vertex === end) {
return path;
}
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
visited.add(neighbor.node);
queue.push([neighbor.node, [...path, neighbor.node]]);
}
}
}
return null;
}
hasCycle() {
const visited = new Set();
const recursionStack = new Set();
const dfs = (vertex, parent = null) => {
visited.add(vertex);
recursionStack.add(vertex);
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
const nextVertex = neighbor.node;
if (this.isDirected && visited.has(nextVertex) && recursionStack.has(nextVertex)) {
return true;
}
if (!this.isDirected && nextVertex === parent) {
continue;
}
if (!visited.has(nextVertex)) {
if (dfs(nextVertex, vertex)) {
return true;
}
}
}
recursionStack.delete(vertex);
return false;
};
for (let vertex of this.adjacencyList.keys()) {
if (!visited.has(vertex)) {
if (dfs(vertex)) {
return true;
}
}
}
return false;
}
countConnectedComponents() {
const visited = new Set();
let count = 0;
const dfs = (vertex) => {
visited.add(vertex);
const neighbors = this.getNeighbors(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor.node)) {
dfs(neighbor.node);
}
}
};
for (let vertex of this.adjacencyList.keys()) {
if (!visited.has(vertex)) {
dfs(vertex);
count++;
}
}
return count;
}
display() {
for (let [vertex, neighbors] of this.adjacencyList) {
console.log(`${vertex} →`, neighbors.map(n => n.node).join(', '));
}
}
}
Заключение
DFS и BFS — это фундаментальные алгоритмы для работы с графами. Оба работают за O(V+E) и выбор между ними зависит от задачи:
Выбирай DFS если нужно искать пути, обнаруживать циклы или когда память важна
Выбирай BFS если нужен кратчайший путь в невзвешённом графе или слойный обход
Практикуйся с примерами выше, экспериментируй с разными топологиями графов, и вскоре эти алгоритмы станут второй натурой.
