Графы: представления, свойства и выбор структуры

Почти все структуры, которые мы разбирали раньше, описывают данные одной формы: массив — это последовательность, дерево — иерархия, хеш-таблица — множество независимых ключей. Граф не описывает форму — он описывает отношения. Именно поэтому граф оказывается универсальным языком: список — это граф-цепочка, дерево — связный граф без циклов, а таблица зависимостей в вашем сборщике проекта, карта дорог, граф вызовов функций, соцсеть, схема БД с внешними ключами и граф блокировок в СУБД — это буквально одна и та же математическая сущность.

И вот главный практический сюжет: у графа нет «правильного» представления в памяти. У массива есть очевидная раскладка, у бинарной кучи — тоже (мы её разбирали). У графа же есть как минимум пять способов хранения, и разница между ними — не «в два раза», а в три-четыре порядка по памяти и в десятки раз по скорости обхода. Выбрать неправильно — значит получить сервис, который падает по OOM на графе, который спокойно помещается в ноутбук.

Эта статья — про то, как устроены представления, как считать их реальную цену и как выбирать. Мы почти не будем говорить про алгоритмы на графах (кратчайшие пути, потоки, паросочетания) — это тема трека «Алгоритмы»; здесь мы строим фундамент, на котором они работают.

Предполагается знакомство с асимптотикой и моделью памяти, динамическими массивами, хеш-таблицами и очередями.

Словарь: минимум терминов, без которых дальше нельзя

Граф — это пара G = (V, E): множество вершин V и множество рёбер E ⊆ V × V. Всё остальное — это уточнения, каждое из которых меняет выбор структуры хранения:

• Ориентированность. В неориентированном графе ребро {u, v} симметрично: дружба. В ориентированном дуга (u, v) ≠ (v, u): подписка, зависимость пакета, ссылка на странице. Практическое следствие: неориентированное ребро в списках смежности хранится дважды, и это главный источник ошибок «забыл добавить обратное ребро».
• Веса. Число (или структура) на ребре: длина дороги, пропускная способность, стоимость. Веса надо где-то хранить — и это отдельное решение, а не «просто ещё одно поле».
• Кратные рёбра и петли. Мультиграф допускает несколько рёбер между одной парой (два авиарейса Москва—Сочи с разной ценой), петля — ребро из вершины в себя. Многие «оптимизированные» представления их молча ломают.
• Степень deg(v) — число инцидентных вершине рёбер; для орграфа отдельно indeg и outdeg.
• Плотность. Ключевая величина. Максимум рёбер в простом неориентированном графе — V(V−1)/2 ≈ V²/2. Граф называют разреженным, если E = O(V) или E = O(V log V), и плотным, если E = Θ(V²).

Лемма о рукопожатиях: Σ deg(v) = 2|E|. Тривиально (каждое ребро добавляет по единице двум концам), но это рабочий инструмент: она говорит, что суммарный размер всех списков смежности ровно 2E, а значит полный обход всех списков стоит Θ(V + E), а не Θ(V · maxdeg). Отсюда же следует, что средняя степень в графе равна 2E/V — и если она у вас 8, то любая структура, тратящая 100 байт на вершину сверх рёбер, потратит больше памяти на «обвязку», чем на сами данные.

Каждая ветка этого дерева влияет на выбор структуры: DAG позволяет топологическую сортировку и хранение «вперёд по уровням», двудольность разделяет два массива вершин, статичность разрешает CSR, а полная динамичность — запрещает.

Пять способов хранить граф

Договоримся: вершины пронумерованы 0 .. V-1. Это не мелочь — почти все быстрые представления требуют компактных целочисленных id, и превращение «UUID пользователя → номер» является отдельным обязательным шагом. К нему вернёмся в разделе про прод.

1. Список рёбер (edge list)

Просто массив пар (u, v) (или троек с весом). Память Θ(E), никакой структуры.

Кажется бесполезным — но это самое частое представление на границе системы: так граф приезжает из CSV, из Kafka, из SELECT src, dst FROM edges. Кроме того, целые алгоритмы работают прямо на списке рёбер и ничего другого не требуют: алгоритм Крускала (сортируем рёбра по весу и жадно объединяем компоненты через DSU), алгоритм Беллмана—Форда (V−1 раз проходим по всем рёбрам и релаксируем). Если ваш алгоритм — один из них, не стройте ничего сложнее.

Слабость очевидна: вопрос «кто соседи вершины u?» стоит O(E). Список рёбер не индексирован.

2. Матрица смежности

Двумерный массив A[V][V], где A[u][v] = 1, если ребро есть. Для взвешенного графа — вес (и +∞/sentinel для отсутствующего ребра).

• Проверка «есть ли ребро» — O(1) и, что важнее, одно предсказуемое обращение в память.
• Память Θ(V²) независимо от числа рёбер. Это приговор для больших разреженных графов: при V = 10⁶ матрица из байтов — это 10¹² байт = 1 ТБ.
• Перебор соседей — O(V), даже если сосед один.

Матрица нормализуется до битовой матрицы (V²/8 байт), и вот тогда она внезапно становится конкурентной. При V = 20 000 битовая матрица — это 50 МБ, помещается в RAM, и операции над ней идут пословно: пересечение окрестностей двух вершин (сколько общих друзей) — это popcount(row[u] & row[v]), то есть V/64 машинных слов вместо слияния двух списков. На этом построены быстрые алгоритмы поиска клик и треугольников.

Отдельная красота матрицы — алгебра. Если A — матрица смежности, то (Aᵏ)[u][v] равно числу путей длины ровно k из u в v. Замена «+/×» на «min/+» превращает возведение в степень в алгоритм кратчайших путей; это и есть Флойд—Уоршелл, и это же — идея GraphBLAS: графовые алгоритмы как разреженная линейная алгебра.

3. Списки смежности

Массив длины V, где adj[v] — контейнер соседей v. Классика из учебников; в Python это list[list[int]], в C++ vector<vector<int>>, в NetworkX — dict of dicts.

• Память Θ(V + E) по числу элементов, но с большим постоянным оверхедом: каждый вложенный контейнер — отдельный объект с заголовком, ёмкостью и указателем.
• Перебор соседей — O(deg v). Это то, ради чего всё затевалось.
• Проверка ребра — O(deg v) линейным поиском.
• Вставка ребра — O(1) амортизированно.

Вариант «список соседей — это хеш-множество» (dict[int, set[int]]) даёт O(1) проверку ребра ценой ещё большего оверхода памяти и полной потери локальности. NetworkX выбрал именно этот путь — отсюда его удобство и его же reputation «медленный на миллионах рёбер».

4. CSR — сжатые списки смежности

Compressed Sparse Row (он же forward star, он же packed adjacency): берём все списки смежности и склеиваем их в один плоский массив, а границы блоков храним отдельно.

offset : [0, 2, 5, 7, 10, 12]                        длина V+1
targets: [1,3, 0,2,3, 1,4, 0,1,4, 2,3]               длина 2E
соседи вершины v = targets[offset[v] : offset[v+1]]

Это то же самое представление, что scipy.sparse.csr_matrix использует для разреженных матриц — и не случайно: граф и есть разреженная матрица.

Свойства:

• Память — ровно 4·(V+1) + 4·2E байт при 32-битных id. Никаких заголовков объектов, никаких запасов ёмкости. Обычно в 5–20 раз компактнее list[list[int]].
• Обход соседей — последовательное чтение подряд лежащих ячеек. Префетчер процессора счастлив; это единственное представление, которое действительно упирается в пропускную способность памяти, а не в latency случайных обращений (вспомните иерархию памяти).
• Расплата: структура иммутабельная. Добавить ребро — значит сдвинуть половину массива.

Строится CSR за два прохода, по схеме поразрядной сортировки: посчитать степени → префиксная сумма → разложить.

5. Прочее, о чём стоит знать

• Матрица инцидентности V × E: строки — вершины, столбцы — рёбра. Память Θ(V·E) — хуже всего, но естественно выражает гиперграфы (ребро соединяет произвольное множество вершин) и является канонической формой в задачах линейного программирования и теории потоков.
• Неявный граф. Часто граф вообще не нужно хранить: у лабиринта соседи клетки вычисляются арифметикой, у шахматной позиции — генератором ходов. Функция neighbors(v) — полноценное представление с памятью O(1). Если ваш граф порождается правилом — не материализуйте его.
• Разбиение по хостам / out-of-core. Когда граф не помещается в память: вершины делятся между машинами (Pregel), либо CSR лежит в mmap-файле и читается страницами.

Сводная таблица

Обозначения: V — вершины, E — рёбра, d — степень вершины.

Численный ориентир для перехода: битовая матрица занимает V²/8 байт, CSR с 32-битными id — 8E байт. Они сравниваются при E ≈ V²/64. То есть матрица начинает выигрывать по памяти, когда заполнено больше ~1,5 % клеток. Соцсети (средняя степень 100–500 при V в миллионах) не приближаются к этому порогу и на десять порядков; а вот граф похожести 5000 товаров с 2 млн рёбер — вполне.

Код: один интерфейс, три реализации

Ключевая мысль этой диаграммы: алгоритмы должны зависеть от интерфейса neighbors(v), а не от представления. Тогда переход «прототип на списках смежности → прод на CSR» стоит одну строчку.

from array import array
from typing import Iterable, Iterator


class AdjListGraph:
    """Изменяемый граф на списках смежности. Рабочая лошадка для построения и прототипов."""

    def __init__(self, n: int, directed: bool = False) -> None:
        self.n = n
        self.directed = directed
        self.adj: list[list[int]] = [[] for _ in range(n)]

    def add_edge(self, u: int, v: int) -> None:
        # Неориентированное ребро — это ДВЕ записи. Забыть вторую — ошибка №1 в графовом коде.
        self.adj[u].append(v)
        if not self.directed:
            self.adj[v].append(u)

    def neighbors(self, v: int) -> Iterable[int]:
        return self.adj[v]                      # O(deg v) на обход

    def degree(self, v: int) -> int:
        return len(self.adj[v])

    def has_edge(self, u: int, v: int) -> bool:
        return v in self.adj[u]                 # O(deg u) — линейный поиск!

    def remove_edge(self, u: int, v: int) -> None:
        # swap-remove: порядок соседей не важен, поэтому O(deg) вместо O(deg) со сдвигом
        for lst, a, b in ((self.adj[u], u, v),) if self.directed else (
                (self.adj[u], u, v), (self.adj[v], v, u)):
            i = lst.index(b)
            lst[i] = lst[-1]
            lst.pop()

    def edges(self) -> Iterator[tuple[int, int]]:
        for u in range(self.n):
            for v in self.adj[u]:
                if self.directed or u <= v:     # чтобы не выдать каждое ребро дважды
                    yield (u, v)


class BitMatrixGraph:
    """Матрица смежности на длинных целых Python: одна строка = одно большое число-битмаска."""

    def __init__(self, n: int) -> None:
        self.n = n
        self.rows = [0] * n

    def add_edge(self, u: int, v: int) -> None:
        self.rows[u] |= 1 << v
        self.rows[v] |= 1 << u

    def has_edge(self, u: int, v: int) -> bool:
        return (self.rows[u] >> v) & 1 == 1     # O(1) по числу обращений

    def neighbors(self, v: int) -> Iterator[int]:
        row = self.rows[v]
        while row:                              # обходим только установленные биты
            low = row & -row                    # младший установленный бит
            yield low.bit_length() - 1
            row ^= low

    def common_neighbors(self, u: int, v: int) -> int:
        """Число общих соседей — одно И и один popcount вместо слияния двух списков."""
        return (self.rows[u] & self.rows[v]).bit_count()   # Python 3.10+


class CSRGraph:
    """Иммутабельный граф в формате CSR: два плоских массива, максимальная локальность."""

    __slots__ = ("n", "offset", "targets")

    def __init__(self, n: int, offset: array, targets: array) -> None:
        self.n = n
        self.offset = offset
        self.targets = targets

    @staticmethod
    def from_edges(n: int, edges: Iterable[tuple[int, int]],
                   directed: bool = False) -> "CSRGraph":
        """Сборка за два прохода: подсчёт степеней -> префиксная сумма -> раскладка. O(V + E)."""
        edges = list(edges)

        # Проход 1: степени
        deg = array("i", bytes(4 * n))
        for u, v in edges:
            deg[u] += 1
            if not directed:
                deg[v] += 1

        # Префиксная сумма -> границы блоков (offset[v] — начало блока вершины v)
        offset = array("i", bytes(4 * (n + 1)))
        total = 0
        for v in range(n):
            offset[v] = total
            total += deg[v]
        offset[n] = total

        # Проход 2: раскладка. cursor[v] — куда писать следующего соседа v.
        targets = array("i", bytes(4 * total))
        cursor = array("i", offset[:n])
        for u, v in edges:
            targets[cursor[u]] = v
            cursor[u] += 1
            if not directed:
                targets[cursor[v]] = u
                cursor[v] += 1

        return CSRGraph(n, offset, targets)

    def neighbors(self, v: int) -> memoryview:
        # Срез подряд лежащих ячеек — идеальный паттерн доступа для кеша
        return memoryview(self.targets)[self.offset[v]:self.offset[v + 1]]

    def degree(self, v: int) -> int:
        return self.offset[v + 1] - self.offset[v]

    def sort_adjacency(self) -> None:
        """Отсортировать соседей внутри блоков: включает бинарный поиск и дешёвые пересечения."""
        for v in range(self.n):
            lo, hi = self.offset[v], self.offset[v + 1]
            self.targets[lo:hi] = array("i", sorted(self.targets[lo:hi]))

    def has_edge(self, u: int, v: int) -> bool:
        """O(log deg u) — только если предварительно вызван sort_adjacency()."""
        import bisect
        lo, hi = self.offset[u], self.offset[u + 1]
        i = bisect.bisect_left(self.targets, v, lo, hi)
        return i < hi and self.targets[i] == v

    def transpose(self) -> "CSRGraph":
        """Обратный орграф — тот же двухпроходный трюк. Нужен для SCC, PageRank, обратных ссылок."""
        rev = ((v, u) for u in range(self.n) for v in self.neighbors(u))
        return CSRGraph.from_edges(self.n, rev, directed=True)

Анализ. from_edges делает два линейных прохода по рёбрам и один по вершинам: время Θ(V + E), дополнительная память Θ(V) под deg/cursor. Никаких реаллокаций — размеры известны заранее. neighbors — O(1) на получение среза и O(deg) на обход, degree — O(1). sort_adjacency — Θ(Σ deg log deg) = O(E log E) в худшем случае.

Свойства графа: что и как из него извлекать

Представление выбирают под операции, а операций на графе, в сущности, немного. Почти все базовые свойства извлекаются одним обходом за Θ(V + E).

Классический DFS раскрашивает вершины в три цвета — и это не педантизм, а рабочий механизм: наличие ребра в серую вершину означает обратное ребро, то есть цикл.

from collections import deque

WHITE, GRAY, BLACK = 0, 1, 2


def bfs_distances(g, src: int) -> list[int]:
    """Кратчайшие пути в невзвешенном графе. Θ(V + E) времени, Θ(V) памяти."""
    dist = [-1] * g.n
    dist[src] = 0
    q = deque([src])
    while q:
        u = q.popleft()
        for v in g.neighbors(u):
            if dist[v] == -1:            # проверяем ПЕРЕД добавлением в очередь,
                dist[v] = dist[u] + 1    # иначе вершина попадёт в очередь deg раз
                q.append(v)
    return dist


def is_bipartite(g) -> bool:
    """Двудольность = раскрашиваемость в 2 цвета = отсутствие циклов нечётной длины."""
    color = [-1] * g.n
    for s in range(g.n):
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in g.neighbors(u):
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    q.append(v)
                elif color[v] == color[u]:
                    return False         # ребро внутри доли — нечётный цикл
    return True


def topological_order(g) -> list[int] | None:
    """Итеративный DFS с тремя цветами: топсорт для DAG, None если найден цикл."""
    color = [WHITE] * g.n
    order: list[int] = []
    for s in range(g.n):
        if color[s] != WHITE:
            continue
        stack = [(s, iter(g.neighbors(s)))]
        color[s] = GRAY
        while stack:
            u, it = stack[-1]
            advanced = False
            for v in it:
                if color[v] == GRAY:
                    return None                       # обратное ребро -> цикл
                if color[v] == WHITE:
                    color[v] = GRAY
                    stack.append((v, iter(g.neighbors(v))))
                    advanced = True
                    break
            if not advanced:
                color[u] = BLACK
                order.append(u)
                stack.pop()
    order.reverse()                                   # порядок завершения, развёрнутый
    return order

Три замечания, которые экономят часы отладки:

1. Помечайте вершину при добавлении в очередь, а не при извлечении. Иначе вершина степени d попадёт в очередь d раз, память вырастет до O(E), а на плотном графе процесс «зависнет».
2. Итеративный DFS, а не рекурсивный. У Python лимит рекурсии ~1000; на графе-цепочке из 10⁶ вершин рекурсивный DFS падает. То же касается JVM и Go при глубоком стеке.
3. Компоненты связности в статическом графе считаются обходом за Θ(V + E) — DSU для этого не нужен. DSU выигрывает, когда рёбра приходят по одному и связность надо знать онлайн; об этом — в следующей статье.

Как выбирать представление

Ту же развилку удобно видеть как две независимые оси — плотность и изменчивость:

Практическое правило, которое покрывает 80 % случаев: стройте на списках смежности, замораживайте в CSR. Фаза загрузки редко является узким местом, а фаза запросов работает годами.

Что ломается в реальности

Асимптотика говорит, что списки смежности и CSR «одинаковые — Θ(V + E)». На практике разница в 5–15 раз, и вот откуда она берётся.

Оверхед объектов. list[list[int]] в CPython при V = 10⁶ и E = 10⁷: каждый вложенный список — 56 байт заголовка плюс массив указателей (8 байт на элемент) плюс сам объект int (28 байт, если вне кеша малых целых). Итого порядка 400 МБ на структуру и ещё сотни мегабайт на числа. Тот же граф в CSR с int32: 4·(10⁶+1) + 4·2·10⁷ ≈ 84 МБ. Разница — примерно в 10 раз, и она вся — в заголовках и указателях, а не в данных.

Локальность. Обход for v in adj[u] в списках прыгает по куче: сначала указатель на объект-список, потом его буфер, потом объекты-числа. Три зависимых промаха кеша на элемент. В CSR — один последовательный поток. При том же числе «операций» разница по времени — обычно 3–8 раз; подробный разбор механики — в статье про модель памяти.

Перекос степеней. Реальные графы почти никогда не однородны: распределение степеней в вебе, соцсетях и цитированиях подчиняется степенному закону (см. классическую работу Faloutsos et al., On Power-Law Relationships of the Internet Topology, SIGCOMM 1999). Практические следствия жёсткие:

• средняя степень 100 при максимальной 10⁷ — норма; «средний случай» не описывает ничего;
• балансировка при партиционировании по вершинам ломается: одна вершина-суперзвезда перегружает шард;
• BFS от хаба на втором уровне охватывает половину графа — оценки памяти по «средней степени» врут;
• отсюда приёмы вроде direction-optimizing BFS (Beamer, Asanović, Patterson, 2012): на «широком» фронте выгоднее идти не от фронта к соседям, а от непосещённых вершин к фронту — по обратному CSR.

Компактификация id. Внешние идентификаторы (UUID, строки, разреженные int64) обязаны быть переведены в диапазон 0..V-1 — иначе ни матрица, ни CSR не работают, а хеш-таблица на каждом обращении съедает всю выгоду. Стандартный приём — словарь external -> dense на этапе загрузки и обратный массив dense -> external для вывода результатов.

Ширина id. int32 вместо int64 вдвое сокращает targets — а это доминирующий массив. До 2·10⁹ вершин этого хватает. Проверяйте границу явно, тихое переполнение здесь особенно коварно.

Порядок вершин. Перенумерация вершин так, чтобы связанные оказались рядом (обход в ширину, разбиение на кластеры, Gorder), повышает попадание в кеш и даёт ускорение на 1,5–3× без единого изменения алгоритма — см. Speedup Graph Processing by Graph Ordering (Wei et al., SIGMOD 2016, dl.acm.org/doi/10.1145/2882903.2915220). Хранение разностей соседей вместо самих id плюс переменная длина кода (приём из Ligra+/WebGraph) сжимает targets ещё в 2–4 раза.

Хранение весов. В CSR веса кладут в параллельный массив weights[] той же длины, что targets[], а не в массив структур. Тогда алгоритмы, которым веса не нужны (BFS, компоненты), не таскают их через кеш.

Типичные ошибки

1. Забыть обратное ребро в неориентированном графе. Симптом: обход находит лишь часть графа.
2. Считать, что Θ(V + E) — это про списки, а не про матрицу. На матрице тот же BFS стоит Θ(V²), потому что перебор соседей — это строка целиком. На V = 50 000 это 2,5·10⁹ проверок.
3. has_edge в горячем цикле на списках смежности. Выглядит как O(1), стоит O(d). Классический способ превратить «подсчёт треугольников за O(E·d)» в O(E·d²). Лечится сортировкой соседей с бинарным поиском или битовыми масками окрестностей.
4. Пометка вершины при извлечении из очереди, а не при добавлении (см. выше).
5. Рекурсивный DFS на глубоком графе — переполнение стека.
6. Дубликаты и петли, приехавшие из данных. (u, v) пришло дважды — степень завышена, PageRank поехал, «количество друзей» врёт. Дедупликация на этапе загрузки — обязательный шаг, а не опциональный: отсортировать targets внутри блока и схлопнуть повторы.
7. Изменение графа во время обхода. Мутация adj[u] при итерации по нему — UB на любом языке.
8. Матрица «на всякий случай» при V = 200 000: 4·10¹⁰ байт. OOM ещё на аллокации.
9. Хранение весов в словаре dict[(u, v)] -> w. Тапл-ключ, хеширование пары, случайный доступ — на порядок медленнее параллельного массива.

Как это устроено в проде

Базы данных и рекурсивные запросы. Самый частый прод-граф вообще не выглядит как граф: это таблица с self-reference.

Обход такого графа делается рекурсивным CTE — по сути BFS, выполняемый движком БД (PostgreSQL WITH RECURSIVE):

-- Все вершины, достижимые из узла 42 не длиннее чем за 3 шага.
WITH RECURSIVE reachable(node, depth) AS (
    SELECT 42, 0
  UNION                       -- UNION, а не UNION ALL: он отсекает повторные посещения
    SELECT e.dst, r.depth + 1
    FROM reachable r
    JOIN edge e ON e.src = r.node
    WHERE r.depth < 3
)
SELECT node, min(depth) AS dist FROM reachable GROUP BY node;

Здесь ключевая деталь производительности — индекс (src, dst): без него каждый шаг обхода превращается в seq scan по всей таблице рёбер. Фактически индекс B-дерева (мы их разбирали) играет роль списка смежности: соседи вершины лежат рядом в листьях. Именно поэтому графовые СУБД вроде Neo4j продвигают index-free adjacency — узел физически хранит указатели на свои рёбра, что убирает поиск по индексу на каждом шаге и делает стоимость обхода независимой от размера графа.

Аналитика и научные вычисления. scipy.sparse.csr_matrix (документация) — это буквально CSR из этой статьи; scipy.sparse.csgraph даёт на нём BFS, Дейкстру и компоненты связности. igraph и graph-tool хранят CSR в C/C++ и дают Python-обёртку; NetworkX хранит dict of dicts — максимально гибко, но на порядок медленнее и тяжелее по памяти. Практическое правило: NetworkX — до сотен тысяч рёбер, дальше — igraph/graph-tool/CSR вручную.

Большие распределённые графы. Модель Pregel (Google, SIGMOD 2010, research.google/pubs/pregel) — «думай как вершина»: граф партиционирован по вершинам, вычисление идёт супершагами с обменом сообщениями по рёбрам. Из неё выросли Apache Giraph и Spark GraphX. Внутри каждого воркера граф всё равно лежит в CSR. Для одной большой машины альтернатива — shared-memory фреймворки (Ligra, pdf), которые переключаются между push- и pull-обходом в зависимости от размера фронта.

Онлайн-граф соцсети. Facebook TAO (USENIX ATC 2013) — геораспределённый кеш графа поверх MySQL, где основная операция — «дай мне список рёбер типа T из объекта X, отсортированный по времени, первые 50». Заметьте: это не «обход графа», а «список смежности с пагинацией» — 99 % продовых графовых нагрузок именно такие, и оптимизировать надо их, а не алгоритмы обхода.

Библиотеки в языках. Boost.Graph в C++ параметризует представление через adjacency_list<OutEdgeList, VertexList> — вы буквально выбираете vecS/listS/setS для каждого уровня и получаете разные trade-offs. petgraph в Rust предлагает Graph (списки на арене), StableGraph (устойчивые индексы) и Csr. System.Collections в .NET и стандартная библиотека Go графов не содержат — их пишут руками, и это нормально: граф — слишком вариативная структура, чтобы иметь одну каноническую реализацию.

Мини-итог

• Граф — это отношения, а не форма; поэтому у него нет единственного правильного представления.
• Считайте плотность: E против V²/64. Ниже порога — списки/CSR, выше — битовая матрица.
• Считайте изменчивость: если граф после загрузки только читают — замораживайте в CSR, это выигрыш ~10× по памяти и 3–8× по времени обхода, бесплатно.
• Асимптотика Θ(V + E) одинакова у списков и CSR — разницу делают оверхед объектов и локальность.
• Реальные графы имеют степенное распределение степеней: «средняя степень» ничего не описывает, и планировать по ней память и партиционирование нельзя.
• Пишите алгоритмы против интерфейса neighbors(v) — тогда смена представления ничего не сломает.

Источники

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4-е изд., гл. 20 «Elementary Graph Algorithms» — представления, BFS/DFS, топологическая сортировка. mitpress.mit.edu
• Sedgewick, Wayne. Algorithms, 4-е изд., гл. 4 «Graphs» — с полным кодом и разбором API. algs4.cs.princeton.edu/40graphs
• Skiena. The Algorithm Design Manual, гл. 7 — «war stories» о выборе представления. algorist.com
• Malewicz et al. Pregel: A System for Large-Scale Graph Processing, SIGMOD 2010. research.google
• Shun, Blelloch. Ligra: A Lightweight Graph Processing Framework for Shared Memory, PPoPP 2013. pdf
• Wei et al. Speedup Graph Processing by Graph Ordering, SIGMOD 2016. dl.acm.org
• Bronson et al. TAO: Facebook’s Distributed Data Store for the Social Graph, USENIX ATC 2013. usenix.org
• GraphBLAS — стандарт «графовые алгоритмы как линейная алгебра».
• SNAP Datasets — реальные графы для бенчмарков.
• Документация: scipy.sparse, NetworkX, Boost.Graph, petgraph.

Что дальше

Мы научились хранить граф и извлекать его свойства обходом. Но есть класс задач, где рёбра приходят по одному, а ответ на вопрос «в одной ли компоненте эти две вершины?» нужен сразу — и перезапускать обход после каждого ребра слишком дорого. Для этого существует отдельная, удивительно маленькая и удивительно быстрая структура.

Дальше — Система непересекающихся множеств (DSU): две эвристики, обратная функция Аккермана и почему это одна из красивейших структур данных.