Граф: основы

Граф (graph) — абстрактная структура данных, состоящая из множества вершин (nodes/vertices) и рёбер (edges), соединяющих пары вершин.

Зачем нужно

Графы — одна из самых универсальных структур данных: социальные сети, карты дорог, зависимости модулей, сети — всё это графы. Знание основ графов и алгоритмов на них критично для решения задач оптимизации, маршрутизации и анализа связей.

Где используется

  • Социальные сети: граф друзей, рекомендации (друзья друзей)
  • Картографические сервисы: граф дорог, поиск маршрута
  • Пакетные менеджеры: граф зависимостей (npm, pip)
  • Базы данных: граф-базы данных (Neo4j)
  • Компиляторы: граф потока данных, обнаружение циклических зависимостей

Основной контент

Основные термины

  • Вершина (vertex/node): узел графа
  • Ребро (edge): связь между двумя вершинами
  • Ориентированный граф (directed/digraph): рёбра имеют направление (A → B ≠ B → A)
  • Взвешенный граф (weighted): рёбра имеют числовой вес
  • Степень вершины (degree): число рёбер, инцидентных вершине
  • Путь (path): последовательность вершин, соединённых рёбрами
  • Цикл (cycle): путь, начинающийся и заканчивающийся в одной вершине
  • Связный граф: между любыми двумя вершинами есть путь

Способы представления

Список смежности (Adjacency List) — предпочтителен для разреженных графов

// Неориентированный граф
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

// Через Map для динамического добавления
class Graph {
  constructor { this.adj = new Map(); }

  addVertex(v) {
    if (!this.adj.has(v)) this.adj.set(v, );
  }

  addEdge(u, v) { // неориентированный
    this.addVertex(u); this.addVertex(v);
    this.adj.get(u).push(v);
    this.adj.get(v).push(u);
  }

  neighbors(v) { return this.adj.get(v) || ; }
}

Матрица смежности (Adjacency Matrix) — для плотных графов

// n×n матрица: matrix[i][j] = 1 если есть ребро i→j
const n = 4;
const matrix = Array.from({ length: n }, () => new Array(n).fill(0));
matrix[0][1] = 1; // ребро 0→1
matrix[1][2] = 1; // ребро 1→2
// Поиск соседей: O(n) — перебор строки
// Проверка ребра: O(1)
// Память: O(n²)

Сравнение представлений

Критерий Список смежности Матрица смежности
Память O(V + E) O(V^2)
Проверка ребра O(degree) O(1)
Все соседи O(degree) O(V)
Когда использовать Разреженные графы Плотные графы, быстрая проверка ребра

Виды графов

Неориентированный:    A — B — D
                      |
                      C

Ориентированный:      A → B → D
                      ↓
                      C

Взвешенный:           A —(4)— B
                      |       |
                     (2)     (3)
                      |       |
                      C —(1)— D

DAG (directed acyclic graph): ориентированный без циклов
Дерево: связный граф без циклов

Частые ошибки

  • Забывать отмечать посещённые вершины в BFS/DFS — бесконечный цикл при наличии циклов в графе.
  • Использовать матрицу смежности для разреженных графов с тысячами вершин — O(V^2) памяти неприемлемо.
  • Путать ориентированный и неориентированный граф: при добавлении ребра в неориентированный нужно добавлять оба направления.
  • Считать, что граф обязательно связный — могут быть изолированные вершины и компоненты связности.

Связанные темы

Ресурсы