Графы: представления

Граф — это структура данных, состоящая из множества вершин (nodes, vertices) и рёбер (edges), соединяющих эти вершины. Графы моделируют реальные системы: социальные сети (люди = вершины, дружба = рёбра), карты дорог (города = вершины, дороги = рёбра), интернет (компьютеры = вершины, соединения = рёбра), зависимости пакетов, транзакции, молекулярные структуры. Работа с графами — фундаментальный навык для решения системных и алгоритмических задач на Senior/Tech Lead уровне.

Графы бывают ориентированными (directed) и неориентированными (undirected). В ориентированном графе ребро (A, B) — это односторонняя связь A → B. В неориентированном ребро (A, B) означает двустороннюю связь A ↔ B. Графы могут быть взвешенными (weighted), где каждое ребро имеет вес (стоимость, расстояние, время), или невзвешенными, где все рёбра равнозначны. Граф может содержать циклы или быть ациклическим (DAG — directed acyclic graph).

Когда применять / Мотивация

Идея / Как работает

Есть три основных способа представления графа в памяти: adjacency list (список смежности), adjacency matrix (матрица смежности) и edge list (список рёбер). Каждое представление имеет свои trade-offs по памяти и времени доступа.

Adjacency list — самое популярное представление. Для каждой вершины храним список её соседей. В JavaScript это может быть Map<number, Set<number>> или Array<Array<number>>. Память: O(V + E), где V — число вершин, E — число рёбер. Проверка наличия ребра (u, v): O(степень вершины u). Обход всех соседей: O(степень u). Идеально для разреженных графов (sparse graphs), где E << V².

Adjacency matrix — двумерный массив matrix[u][v], где значение означает наличие ребра (0/1 для невзвешенного, вес для взвешенного). Память: O(V²). Проверка ребра: O(1). Добавление ребра: O(1). Обход всех соседей: O(V). Идеально для плотных графов (dense graphs), где E ≈ V², или когда нужны частые запросы «есть ли ребро (u, v)?». Минус — большое потребление памяти даже для разреженных графов.

Edge list — просто массив рёбер [[u1, v1, w1], [u2, v2, w2], ...]. Память: O(E). Используется в алгоритме Kruskal (MST), Union-Find задачах, когда нужно отсортировать рёбра или обработать их последовательно. Минус — нет быстрого доступа к соседям вершины (нужен дополнительный индекс).

Представление	Память	Проверка ребра	Обход соседей	Применение
Adjacency list	O(V+E)	O(deg)	O(deg)	Sparse graphs, BFS/DFS
Adjacency matrix	O(V²)	O(1)	O(V)	Dense graphs, Floyd-Warshall
Edge list	O(E)	O(E)	O(E)	Kruskal, Union-Find

Реализация

Задача: Number of Connected Components in Undirected Graph

Дан неориентированный граф из n вершин (нумерация 0..n-1) и список рёбер edges. Найти количество связных компонент в графе. Связная компонента — это максимальное подмножество вершин, где любые две вершины достижимы друг от друга.

Подход и идея решения

Эта задача — классический пример применения обхода графа. Главная идея: запускаем DFS или BFS из каждой непосещённой вершины, помечая все достижимые вершины как посещённые. Каждый запуск обхода «открывает» одну связную компоненту. Число запусков = число компонент.

Шаг 1: построить adjacency list из списка рёбер. Для неориентированного графа каждое ребро (u, v) добавляем в оба направления: graph[u].add(v) и graph[v].add(u).

Шаг 2: инициализировать множество посещённых вершин visited. Пройти все вершины от 0 до n-1: если вершина не посещена, запустить DFS и увеличить счётчик компонент. DFS помечает все достижимые вершины, т.е. всю связную компоненту.

Этот паттерн «запустить обход из каждой непосещённой вершины» встречается в задачах: Number of Islands, Friend Circles, Connected Components, Coloring Graph.

function countComponents(n, edges) {
    // Шаг 1: построить adjacency list
    const graph = new Map();
    for (let i = 0; i < n; i++) {
      graph.set(i, new Set());
    }

    for (const [u, v] of edges) {
      graph.get(u).add(v);
      graph.get(v).add(u); // неориентированный граф
    }

    // Шаг 2: обход графа с подсчётом компонент
    const visited = new Set();
    let count = 0;

    function dfs(node) {
      visited.add(node);
      for (const neighbor of graph.get(node)) {
        if (!visited.has(neighbor)) {
          dfs(neighbor);
        }
      }
    }

    for (let i = 0; i < n; i++) {
      if (!visited.has(i)) {
        dfs(i);
        count++;
      }
    }

    return count;
  }

Трассировка

Трассировка: n = 5, edges = [[0,1], [1,2], [3,4]]

Граф:

    0 --- 1 --- 2        3 --- 4

Построение adjacency list: - graph[0] = {1}, graph[1] = {0, 2}, graph[2] = {1} - graph[3] = {4}, graph[4] = {3}
i=0: не посещён → dfs(0) - dfs(0): visited={0}, идём к 1 - dfs(1): visited={0,1}, идём к 2 (0 уже посещён) - dfs(2): visited={0,1,2}, соседей нет count = 1
i=1,2: уже посещены → skip
i=3: не посещён → dfs(3) - dfs(3): visited={0,1,2,3}, идём к 4 - dfs(4): visited={0,1,2,3,4}, соседей нет count = 2
i=4: уже посещён → skip

Результат: 2 компоненты ✓

Сложность

Анализ сложности:

Time: O(V + E) - Построение adjacency list: O(E) (каждое ребро обрабатываем дважды) - DFS: посещаем каждую вершину один раз O(V), для каждой вершины обходим всех соседей (суммарно O(E))
Space: O(V + E) - Adjacency list: O(V + E) - visited set: O(V) - Стек рекурсии: O(V) в худшем случае (граф = длинная цепь)

Почему O(V + E), а не O(V · E)? Потому что каждое ребро обрабатывается ровно дважды (один раз с каждого конца), а каждая вершина посещается один раз.

Выбор представления критичен для производительности. Для большинства задач на интервью используется adjacency list — он даёт оптимальный баланс памяти и скорости для типичных графов с E = O(V) или E = O(V log V).

Типичные ошибки и подводные камни

Изолированные вершины: Если у вершины нет рёбер, она сама по себе — связная компонента. Наш код корректно обрабатывает это (каждая непосещённая вершина → +1 компонента).
Self-loops: Ребро (u, u). Для подсчёта компонент не имеет значения. В других задачах (cycle detection) может требовать особой обработки.
Parallel edges: Несколько рёбер между одной парой вершин. Set автоматически дедуплицирует соседей, так что это не проблема.
Stack overflow в DFS: Если граф — длинная цепь (n вершин в линию), глубина рекурсии = n. При n > 10,000 возможен stack overflow в JS. Решение: итеративный DFS с явным стеком или BFS с очередью.
Выбор DFS vs BFS: Для подсчёта компонент оба эквивалентны. DFS компактнее в коде, BFS — безопаснее для глубоких графов (нет stack overflow). Для кратчайшего пути в невзвешенном графе — только BFS.
Интервьюер спросит: «Можно ли использовать Union-Find?» — Да! DSU идеально подходит: для каждого ребра делаем union(u, v), в конце считаем число корней. O(E·α(V)) ≈ O(E), но проще код и подходит для динамических запросов.

Follow-up вопросы интервьюера

Directed vs Undirected: Как изменится решение для ориентированного графа? — Понятие «связная компонента» заменяется на «сильно связная компонента» (strongly connected component, SCC). Алгоритм: Tarjan или Kosaraju, O(V+E).
Number of Islands (матрица 0/1): Найти число островов в матрице, где 1 — суша, 0 — вода. — DFS/BFS по соседям (вверх, вниз, влево, вправо). O(rows·cols).
Clone Graph: Сделать deep copy графа. — DFS/BFS с Map<старый узел, новый узел>. При посещении вершины: если не в Map — создаём копию, добавляем в Map, рекурсивно клонируем соседей.
Graph Valid Tree: Проверить, что граф — дерево (связный + ациклический). — Условия: (1) ровно n-1 рёбер, (2) граф связный (одна компонента), (3) нет циклов (можно проверить через DFS с parent tracking).
Bipartite Graph: Можно ли раскрасить граф в два цвета так, чтобы соседи имели разные цвета? — BFS/DFS с раскраской: помечаем вершину цветом 0, соседей цветом 1, их соседей — 0, и т.д. Если встретили ребро между вершинами одного цвета → не bipartite.
Trade-offs представлений: Когда использовать матрицу вместо списка? — Матрица: плотный граф (E ≈ V²), частые запросы «есть ли ребро», фиксированный размер V. Список: sparse graph, динамическое добавление вершин, обход соседей.

Чеклист на собес

Чётко спросил у интервьюера: ориентированный или неориентированный? взвешенный? есть ли self-loops, parallel edges?
Оценил плотность графа (sparse vs dense) перед выбором представления — это решает adjacency list vs matrix.
Для большинства задач по умолчанию использую adjacency list (Map<number, Set<number>> или массив массивов).
Проговорил Time/Space обхода: O(V + E) для DFS/BFS, O(V²) если используется матрица.
Не забыл обработать изолированные вершины — они тоже компоненты связности.
Если граф большой и глубина рекурсии может превысить ~10⁴ — переключаюсь на итеративный DFS со стеком или BFS.
Обсудил альтернативу: для задач связности готов предложить Union-Find как более элегантный способ.