Представление графов 🕸️
В прошлом уроке граф был математическим объектом: множество вершин $V$ и множество рёбер $E$, абстракция, которую удобно рисовать на бумаге в виде точек и линий. Но компьютер не умеет рисовать точки и линии — он умеет только читать и записывать байты по адресам в памяти. Прежде чем к графу можно применить хоть один алгоритм — найти путь, посчитать компоненты связности, обучить нейросеть, — граф нужно превратить в конкретную структуру данных: массив, список, таблицу. Этот перевод от математической абстракции к структуре в памяти и есть тема этого урока, и от того, как именно он сделан, зависит не только скорость программы, но и то, поместится ли граф в память вообще.
Здесь есть прямая и не всегда очевидная связь с машинным обучением. Когда графовая нейросеть (Graph Neural Network, GNN) обрабатывает граф — молекулу, социальную сеть, граф цитирований научных статей, — на вход ей буквально подаётся матрица смежности (или её разреженный эквивалент) вместе с матрицей признаков вершин. Один из самых влиятельных слоёв графовых нейросетей, графовый свёрточный слой, в оригинальной статье Кипфа и Уэллинга 2017 года записывается формулой $H' = \sigma(\hat{A} H W)$, где $\hat{A}$ — это (нормализованная) матрица смежности графа. То есть структура данных, которую ты изучишь в этом уроке как «просто способ хранения графа», оказывается на практике буквальным математическим объектом, который умножается на матрицу весов внутри нейросети. Понимание того, что такое матрица смежности, — это не абстрактная теория, а прямой путь к пониманию того, как вообще устроен вход GNN.
Но у этой связи есть обратная, не менее важная сторона. Реальные графы, с которыми работают на практике — графы социальных сетей с миллиардами пользователей, графы знаний вроде Wikidata с сотнями миллионов сущностей, графы молекул с десятками атомов, — почти никогда не бывают плотными: у типичного пользователя соцсети сотни друзей, а не миллиарды, у типичного атома в молекуле несколько химических связей, а не связь с каждым другим атомом. Матрица смежности для такого графа будет состоять почти целиком из нулей, и хранить эти нули явно — это не просто неэффективно, а физически невозможно уже при относительно скромных размерах графа. Именно поэтому промышленные библиотеки для GNN (PyTorch Geometric, DGL) на практике никогда не хранят графы как плотные матрицы — они используют разреженное представление, концептуальный родственник списка смежности, о котором пойдёт речь во второй половине этого урока.
Итак, план на этот урок: сначала подробно разберём два основных способа представления графа — матрицу смежности и список смежности, — каждый со своей интуицией, формальным определением и разобранными примерами. Затем сравним их напрямую и научимся быстро определять, какое представление подходит для конкретной задачи, исходя из плотности графа. Наконец, разберёмся, как оба подхода расширяются на взвешенные графы, и коротко познакомимся с третьим, более компактным вариантом представления — списком рёбер, который лежит в основе того самого формата, который используют современные библиотеки глубокого обучения на графах.
История: от бумаги к байтам
Формальная теория графов родилась в 1736 году, когда Леонард Эйлер решил задачу о семи мостах Кёнигсберга, но почти два века после этого граф оставался чисто математическим объектом — его изучали на бумаге, доказывали теоремы о нём, рисовали схемы, но вопрос «как эффективно хранить граф в памяти вычислительного устройства» просто не стоял, потому что вычислительных устройств, способных обрабатывать граф произвольного размера, ещё не существовало. Первые серьёзные попытки формализовать представление графа для вычислений появились вместе с развитием теории алгоритмов и структур данных в 1950–1960-х годах, когда графовые задачи (поиск кратчайшего пути, построение минимального остовного дерева, анализ электрических цепей) стали одними из первых практических приложений зарождающейся информатики. Именно тогда матрица смежности — самый прямолинейный способ «оцифровать» граф, буквально таблица из нулей и единиц — стала стандартным учебным представлением: она проста для доказательства теорем, удобна для матричной алгебры (степени матрицы смежности считают число путей заданной длины) и естественно вписывалась в вычислительные машины той эпохи, которые и так были устроены вокруг работы с массивами и таблицами чисел.
Список смежности как альтернатива появился не потому, что кто-то придумал более «умную» идею, а потому, что реальные графы, с которыми столкнулись программисты уже в 1960–1970-е годы — графы транспортных сетей, графы электрических схем, графы зависимостей в программах компиляторов, — оказались катастрофически разреженными: число рёбер росло линейно с числом вершин, а не квадратично. Дональд Кнут в первом томе своего фундаментального труда «Искусство программирования» (первое издание — 1968 год) уже подробно разбирает оба представления графа и явно формулирует то, что сегодня кажется очевидным: для разреженного графа хранить явно каждую из $n^2$ потенциальных пар вершин — расточительство, а структура, которая хранит только реально существующие рёбра, экономит на порядки больше памяти. Это была не революция, а трезвый инженерный вывод из наблюдения за тем, как на самом деле устроены графы в реальных задачах.
Настоящий взрыв интереса к разреженным представлениям графов пришёлся на конец XX и начало XXI века, когда появились интернет и социальные сети — графы с миллионами, а затем и миллиардами вершин, у каждой из которых лишь считаные сотни связей. На таких масштабах разница между $O(V^2)$ памятью матрицы смежности и $O(V+E)$ памятью списка смежности перестала быть теоретической тонкостью и стала вопросом «работает программа вообще или нет». Google, строя граф ссылок между веб-страницами для алгоритма PageRank, физически не мог хранить его как плотную матрицу — потребовались бы объёмы памяти, которых не существует ни в одном дата-центре мира. Ровно та же логика двадцать лет спустя привела к тому, что современные графовые нейросети по умолчанию работают с разреженными представлениями графов, а не с плотными матрицами: молекулы в химических датасетах невелики, но графы социальных сетей и графы знаний, на которых обучают промышленные рекомендательные системы, устроены точно так же разреженно, как графы ссылок веб-страниц столетие назад — просто на ещё большем масштабе.
Матрица смежности
Интуиция
Представь себе турнирную таблицу футбольного чемпионата: строки — команды, столбцы — те же команды, а в ячейке на пересечении строки и столбца стоит отметка, если между этими двумя командами была игра. Матрица смежности графа устроена точно так же: это большая таблица размером $V \times V$, где $V$ — число вершин, и ячейка на пересечении строки $i$ и столбца $j$ хранит информацию о том, есть ли ребро между вершиной $i$ и вершиной $j$. Никакой более сложной идеи здесь нет — это самый прямой, «в лоб» способ оцифровать граф: взять каждую возможную пару вершин и явно записать, соединены они или нет.
Ключевое наблюдение, которое стоит держать в голове с самого начала: матрица смежности хранит информацию про все возможные пары вершин, даже про те, между которыми ребра нет. Если в графе из 1000 вершин есть всего 500 рёбер, матрица смежности всё равно будет состоять из миллиона ячеек — и в подавляющем большинстве из них будет записан ноль. Это и есть главная плата за простоту такого представления, к которой мы ещё вернёмся в разделе сравнения.
Формальное определение
Определение. Пусть $G = (V, E)$ — граф с $n = |V|$ вершинами, пронумерованными числами от $0$ до $n-1$. Матрицей смежности графа $G$ называется квадратная матрица $A$ размера $n \times n$, элементы которой определяются как
$$A[i][j] = \begin{cases} 1, & \text{если } (i,j) \in E \\ 0, & \text{если } (i,j) \notin E \end{cases}$$Для неориентированного графа матрица $A$ симметрична: $A[i][j] = A[j][i]$ для любых $i, j$, поскольку ребро $(i,j)$ и ребро $(j,i)$ — одно и то же. Для ориентированного графа это условие в общем случае не выполняется: $A[i][j]=1$ означает наличие дуги из $i$ в $j$, а вовсе не обязательно из $j$ в $i$.
Примеры с разбором
Пример 1. Граф дружбы четырёх учеников. Пусть у нас четыре вершины — Аня (0), Боря (1), Вера (2), Гоша (3), — и три ребра дружбы: Аня–Боря, Аня–Вера, Боря–Гоша. Построим матрицу смежности.
n = 4 # Аня=0, Боря=1, Вера=2, Гоша=3
matrix = [[0] * n for _ in range(n)]
edges = [(0, 1), (0, 2), (1, 3)]
for u, v in edges:
matrix[u][v] = 1
matrix[v][u] = 1 # граф неориентированный — ребро симметрично
for row in matrix:
print(row)
# [0, 1, 1, 0]
# [1, 0, 0, 1]
# [1, 0, 0, 0]
# [0, 1, 0, 0]
Заметь: получившаяся матрица симметрична относительно главной диагонали, как и должно быть для неориентированного графа. Главная диагональ (ячейки $A[i][i]$) состоит из нулей — в этом графе нет рёбер из вершины в саму себя (петель); если бы петли были разрешены, соответствующие диагональные ячейки содержали бы единицу.
Проверка наличия ребра теперь тривиальна и выполняется за одно обращение к памяти:
def has_edge(matrix, u, v):
return matrix[u][v] == 1
print(has_edge(matrix, 0, 1)) # True — Аня и Боря дружат
print(has_edge(matrix, 2, 3)) # False — Вера и Гоша не знакомы
Пример 2. Ориентированный граф ссылок между сайтами. Пусть сайт $A$ ссылается на $B$, сайт $B$ ссылается на $C$, сайт $C$ ссылается на $A$ — классический цикл ссылок, который лежит в основе идеи PageRank.
n = 3 # A=0, B=1, C=2
matrix = [[0] * n for _ in range(n)]
matrix[0][1] = 1 # A -> B
matrix[1][2] = 1 # B -> C
matrix[2][0] = 1 # C -> A
for row in matrix:
print(row)
# [0, 1, 0]
# [0, 0, 1]
# [1, 0, 0]
Здесь матрица уже не симметрична: $A[0][1]=1$ (сайт $A$ ссылается на $B$), но $A[1][0]=0$ (сайт $B$ не ссылается на $A$). Асимметрия матрицы смежности — это ровно то, что отличает представление ориентированного графа от неориентированного: если проверить матрицу на симметрию и обнаружить хоть одно нарушение $A[i][j] \ne A[j][i]$, это верный признак, что граф ориентированный.
Пример 3. Матрица смежности как вход графовой нейросети. Этот пример — прямая иллюстрация связи, заявленной во вступлении. Базовая операция графовой свёрточной сети — это агрегация признаков соседей каждой вершины, и для матрицы признаков $X$ размера $V \times F$ (где $F$ — число признаков на вершину) один шаг такой агрегации записывается как обычное матричное умножение $A \cdot X$.
import numpy as np
A = np.array([[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 0],
[0, 1, 0, 0]]) # та же матрица, что в примере 1
X = np.array([[1.0, 0.5],
[0.2, 0.8],
[0.9, 0.1],
[0.4, 0.4]]) # 4 вершины, по 2 признака у каждой
H = A @ X
print(H)
# строка 0 (Аня) = сумма признаков соседей (Бори и Веры) = [0.2+0.9, 0.8+0.1] = [1.1, 0.9]
Строка $H[0]$ получилась как сумма признаков вершин-соседей вершины $0$ — именно потому, что строка матрицы смежности $A[0]$ содержит единицы ровно в позициях соседей. Это и есть операция message passing («передачи сообщений») в её простейшем виде: каждая вершина собирает информацию от своих соседей, а матрица смежности — это буквально тот объект, который управляет тем, кто с кем «обменивается сообщениями». Более развитые архитектуры GNN добавляют нормализацию (степень вершины учитывается, чтобы вершины с большим числом соседей не «перевешивали» вклад), обучаемые веса $W$ и нелинейность $\sigma$, но фундаментальная операция — умножение на матрицу смежности — остаётся прежней.
Почему это важно
Матрица смежности даёт то, что не может дать ни одна другая простая структура: проверку наличия конкретного ребра за строго $O(1)$ — одно обращение по индексам к двумерному массиву, без единого сравнения или обхода. Она также естественно вписывается в аппарат линейной алгебры: умножение матрицы смежности саму на себя $A^2$ даёт число путей длины 2 между любой парой вершин, а более сложные операции над $A$ (собственные значения, спектральное разложение) лежат в основе спектральной кластеризации графов и анализа их структуры — направления, активно используемого в анализе социальных сетей и в некоторых архитектурах GNN. Но за эту скорость доступа и математическую элегантность приходится платить: матрица занимает $O(V^2)$ памяти независимо от того, сколько в графе реально рёбер — даже для графа, где рёбер почти нет, придётся выделить и хранить полную таблицу из $V^2$ ячеек.
Список смежности
Интуиция
Представь телефонную книгу, устроенную не по алфавиту, а по принципу «для каждого человека — список тех, кому он звонит». Список смежности графа устроен ровно так: для каждой вершины хранится отдельный, компактный список её соседей, и ничего больше. Если у вершины пять соседей, для неё хранится список из пяти элементов; если у вершины миллион соседей — список из миллиона элементов; если соседей нет вовсе — список пуст. В отличие от матрицы смежности, здесь никогда не тратится память на пары вершин, между которыми ребра нет: список просто не содержит записи про отсутствующую связь, вместо того чтобы явно хранить в этом месте ноль.
Это единственное отличие — не тратить память на «отсутствие» — оказывается решающим, как только граф становится большим и разреженным, а таких графов в реальном мире подавляющее большинство: у среднего пользователя социальной сети не миллиард друзей, а несколько сотен; у среднего сайта в интернете исходящие ссылки ведут не на миллиарды других страниц, а на десятки-сотни.
Формальное определение
Определение. Пусть $G = (V,E)$ — граф с вершинами, пронумерованными от $0$ до $n-1$. Список смежности — это структура $L$, состоящая из $n$ списков (по одному на вершину), где $L[i]$ содержит все вершины $j$, такие что $(i,j) \in E$:
$$L[i] = \{\, j : (i,j) \in E \,\}.$$На практике список смежности реализуют как массив (или словарь) списков, множеств, либо связных списков — в зависимости от того, какие операции над соседями нужны чаще: список даёт компактность и порядок вставки, множество — быструю проверку наличия конкретного соседа.
Примеры с разбором
Пример 1. Тот же граф дружбы, теперь как список смежности. Используем те же данные, что в первом примере матрицы смежности.
from collections import defaultdict
adj = defaultdict(list)
edges = [(0, 1), (0, 2), (1, 3)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
print(dict(adj))
# {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}
Сравни с матрицей из первого примера предыдущего раздела: там пришлось хранить $4 \times 4 = 16$ ячеек, из которых лишь $6$ содержали единицу (по три ребра, каждое встречается дважды из-за симметрии), а $10$ — нули. Здесь список хранит ровно $6$ записей о соседях — ни одной лишней, потому что «отсутствие ребра» никак не занимает память, оно просто не упомянуто.
Пример 2. Расчёт памяти для графа социальной сети. Пусть в графе $V = 10^9$ вершин (пользователей) и в среднем $200$ связей на пользователя. Посчитаем и сравним память для обоих представлений.
Матрица смежности (даже в самом компактном варианте — по одному биту на ячейку, без учёта накладных расходов): $V^2 = (10^9)^2 = 10^{18}$ ячеек, то есть $10^{18}$ бит $\approx 1{,}25 \times 10^{17}$ байт $\approx 125$ петабайт. Это на много порядков больше суммарного объёма оперативной памяти всех серверов крупного дата-центра.
V = 10**9
degree_avg = 200
id_size_bytes = 8 # 64-битный идентификатор пользователя
matrix_bits = V ** 2
matrix_bytes = matrix_bits / 8
print(f"Матрица: {matrix_bytes:.2e} байт") # 1.25e+17 байт = ~125 петабайт
list_bytes = V * degree_avg * id_size_bytes
print(f"Список: {list_bytes:.2e} байт") # 1.60e+12 байт = ~1.6 терабайта
Список смежности занимает около $1{,}6$ терабайта — объём, который спокойно умещается на нескольких серверах современного дата-центра, а при разбиении графа между машинами (шардировании) — и вовсе на одном узле среднего масштаба. Разница между «125 петабайт» и «1,6 терабайта» — это не разница в удобстве, это разница между «задача решаема» и «задача физически нерешаема» при текущем уровне развития аппаратного обеспечения.
Пример 3. Обход соседей за время, пропорциональное степени вершины. Часто требуется не просто проверить наличие ребра, а перебрать всех соседей вершины — например, чтобы посчитать её степень или запустить обход графа.
def neighbors_list(adj, v):
return adj[v] # O(degree(v)) — читаем ровно нужное число элементов
def neighbors_matrix(matrix, v):
n = len(matrix)
return [u for u in range(n) if matrix[v][u] == 1] # O(n) — приходится пройти всю строку
Для вершины с $5$ соседями в графе из $10^9$ вершин список смежности вернёт результат за $5$ шагов, а обход строки матрицы потребует $10^9$ шагов — даже если реальных соседей всего пять, придётся проверить все остальные $999\,999\,995$ ячеек строки только для того, чтобы убедиться, что там нули. Это принципиальная разница в поведении: список смежности «платит» ровно за то, что реально есть в графе, а матрица — за потенциальную возможность любой связи, вне зависимости от того, реализована она или нет.
Почему это важно
Список смежности — это структура, которую выбирают по умолчанию для подавляющего большинства реальных графов, потому что подавляющее большинство реальных графов разрежено: у вершины реалистично ожидать десятки-сотни соседей, а не сотни миллионов. Именно на списке смежности (или его прямом развитии — разреженной матрице) построены и обходы графа (следующий урок про DFS и BFS целиком опирается на быстрый перебор соседей), и промышленные графовые базы данных, и внутреннее представление графов в библиотеках для GNN. Цена за эту экономию памяти — более медленная (в худшем случае $O(\text{degree})$, а не строго $O(1)$) проверка наличия конкретного ребра между двумя произвольными вершинами, если список соседей не организован как множество; на практике эта цена почти всегда того стоит.
Сравнение подходов: выбор по плотности графа
Интуиция
Ключевая величина, которая определяет, какое представление выгоднее, — это плотность графа: соотношение реального числа рёбер к максимально возможному числу рёбер при данном числе вершин. У полного графа (где каждая вершина соединена с каждой) плотность равна единице — и здесь матрица смежности не тратит впустую вообще ничего, потому что все её ячейки заняты реальными рёбрами. У разреженного графа (типичного для реального мира) плотность близка к нулю — и здесь матрица тратит память почти целиком на хранение отсутствующих связей, тогда как список хранит только то, что реально есть.
Формальное определение
Определение. Для неориентированного графа с $n$ вершинами и $m$ рёбрами плотность определяется как
$$\rho = \frac{m}{\binom{n}{2}} = \frac{2m}{n(n-1)},$$то есть отношение реального числа рёбер к максимально возможному ($\binom{n}{2} = \frac{n(n-1)}{2}$ для простого графа без петель и кратных рёбер). Граф называют плотным (dense), если $m = \Theta(n^2)$ — то есть $\rho$ не стремится к нулю с ростом $n$; граф называют разреженным (sparse), если $m = O(n)$ или $m = O(n \log n)$ — то есть у каждой вершины в среднем ограниченное, не зависящее (или слабо зависящее) от $n$ число соседей.
Примеры с разбором
Пример 1. Плотный граф: расстояния между городами для задачи коммивояжёра. Пусть нужно найти оптимальный маршрут между $N=20$ городами, где расстояние известно между каждой парой городов (прямые рейсы есть отовсюду). Число рёбер здесь $\binom{20}{2}=190$ — почти максимум из возможных $\binom{20}{2}$. Плотность $\rho = 1$: граф полный.
N = 20
max_edges = N * (N - 1) // 2 # 190
actual_edges = 190 # все пары связаны
density = actual_edges / max_edges
print(density) # 1.0 — граф плотный, даже полный
Здесь матрица смежности размером $20 \times 20 = 400$ ячеек — крошечная, полностью оправданная структура: она не тратит память впустую (все связи реальны), а быстрый доступ по индексам $O(1)$ прямо пригождается в алгоритмах вроде динамического программирования Хелда–Карпа для задачи коммивояжёра, которые постоянно обращаются к расстояниям между произвольными парами городов.
Пример 2. Разреженный граф: граф знаний. Пусть граф знаний (например, устроенный по образцу Wikidata) содержит $V = 10^8$ сущностей (людей, мест, понятий), и в среднем у каждой сущности $10$ связей с другими сущностями (родился в, является частью, автор и так далее).
V = 10**8
avg_degree = 10
E = V * avg_degree // 2 # предполагаем граф неориентированным для оценки
matrix_cells = V ** 2
print(f"Матрица: {matrix_cells:.2e} ячеек") # 1.00e+16 — уже нереализуемо
list_entries = V * avg_degree
list_bytes = list_entries * 8
print(f"Список: {list_bytes:.2e} байт") # 8.00e+09 байт = 8 гигабайт
Матрица потребовала бы $10^{16}$ ячеек — даже по биту на ячейку это больше петабайта, притом что реальных связей в графе всего порядка миллиарда. Список смежности занимает около $8$ гигабайт — объём, который умещается в оперативной памяти одного современного сервера. Разница на семь порядков величины — не преувеличение, а прямое следствие формулы $O(V^2)$ против $O(V+E)$ при $E \ll V^2$.
Пример 3. Компромисс: разреженная матрица для матричных операций. Иногда нужен именно матричный интерфейс — например, для той самой операции $A \cdot X$ из графовой нейросети, — но при этом граф разрежен, и плотную матрицу хранить нельзя. Решение — разреженная матрица (sparse matrix), которая хранит только ненулевые элементы, но всё ещё поддерживает матричные операции.
from scipy.sparse import csr_matrix
row = [0, 0, 1, 1, 2, 3]
col = [1, 2, 0, 3, 0, 1]
data = [1] * 6
A_sparse = csr_matrix((data, (row, col)), shape=(4, 4))
print(A_sparse.toarray())
# [[0 1 1 0]
# [1 0 0 1]
# [1 0 0 0]
# [0 1 0 0]]
# память занята только ненулевыми элементами (6 значений + индексы),
# а не всеми 16 ячейками матрицы
print(A_sparse.data.nbytes + A_sparse.indices.nbytes)
Формат CSR (compressed sparse row) хранит только реальные ненулевые элементы вместе с компактными индексами их позиций — по сути, это тот же список смежности, только упакованный так, чтобы над ним можно было проводить стандартные операции линейной алгебры (умножение на вектор, на матрицу) с помощью оптимизированных библиотечных процедур. Именно такой формат (или его близкий родственник — COO, список троек «строка-столбец-значение») используют библиотеки для GNN, когда граф передаётся в нейросеть: PyTorch Geometric хранит граф в формате edge_index — фактически списке рёбер в координатной (COO) форме, — а не в виде плотной матрицы.
Почему это важно
Понимание того, что выбор структуры данных для графа определяется не абстрактными «хорошими практиками», а конкретной плотностью конкретного графа, — это ровно тот навык, который отличает инженерное решение от механического следования шаблону. Для маленького плотного графа (десятки-сотни вершин, где связей почти столько же, сколько возможных пар) матрица смежности — не просто допустимый, а зачастую оптимальный выбор: она проста, даёт $O(1)$ доступ и не тратит память впустую, потому что почти вся память там и занята реальными связями. Для большого разреженного графа (миллионы и миллиарды вершин с ограниченным числом соседей у каждой — типичная картина для социальных сетей, графов знаний, молекулярных графов) матрица смежности не просто неэффективна — она физически не помещается в доступную память уже при относительно скромных по меркам реального мира масштабах, и единственный работающий вариант — список смежности или его матричный эквивалент, разреженная матрица.
Взвешенные графы и список рёбер
Интуиция
До сих пор речь шла о графах, где ребро либо есть, либо его нет — булево, «да/нет» отношение. Но большинство прикладных графов несут дополнительную информацию на каждом ребре: расстояние между городами, вес связи в социальной сети (сила дружбы, число совместных взаимодействий), тип отношения в графе знаний («является отцом», «работает в», «является частью»). Такой граф называется взвешенным, и оба уже разобранных представления расширяются на него почти без усилий: вместо булева флага «ребро есть/нет» в соответствующей ячейке или записи хранится сам вес.
Третий, более компактный способ представить граф — список рёбер — становится особенно естественным именно для взвешенных графов: вместо того чтобы организовывать данные «по вершинам» (как в матрице или списке смежности), можно просто перечислить все рёбра как плоский список троек «откуда, куда, с каким весом».
Формальное определение
Определение. Взвешенная матрица смежности графа $G=(V,E,w)$ с весовой функцией $w: E \to \mathbb{R}$ — это матрица $W$ размера $n \times n$, где $W[i][j] = w(i,j)$, если ребро $(i,j) \in E$, и $W[i][j] = \infty$ (или специальное значение «нет ребра», в зависимости от алгоритма) в противном случае. Взвешенный список смежности — это список $L$, где $L[i]$ содержит пары $(j, w(i,j))$ для каждого соседа $j$ вершины $i$. Список рёбер — это плоский список троек $(u, v, w(u,v))$, по одной на каждое ребро графа, без привязки к конкретной вершине как «владельцу» записи.
Примеры с разбором
Пример 1. Взвешенная матрица дорожной сети. Пусть четыре города соединены дорогами с известными расстояниями: город $0$–город $1$ (5 км), город $1$–город $2$ (3 км).
INF = float('inf')
n = 4
W = [[0 if i == j else INF for j in range(n)] for i in range(n)]
W[0][1] = W[1][0] = 5
W[1][2] = W[2][1] = 3
for row in W:
print(row)
# [0, 5, inf, inf]
# [5, 0, 3, inf]
# [inf, 3, 0, inf]
# [inf, inf, inf, 0]
Значение $\infty$ здесь используется намеренно — так принято в алгоритмах кратчайших путей (например, в алгоритме Флойда–Уоршелла из одного из следующих уроков), где «нет прямой дороги» естественно трактуется как «расстояние бесконечно велико», пока не найден обходной путь.
Пример 2. Взвешенный список смежности той же сети.
from collections import defaultdict
adj_w = defaultdict(list)
adj_w[0].append((1, 5))
adj_w[1].append((0, 5))
adj_w[1].append((2, 3))
adj_w[2].append((1, 3))
print(dict(adj_w))
# {0: [(1, 5)], 1: [(0, 5), (2, 3)], 2: [(1, 3)]}
Каждая запись теперь — не просто номер соседа, а пара «сосед, вес ребра до него». Это представление особенно удобно для алгоритма Дейкстры (разбирается через два урока): чтобы найти кратчайшие пути из одной вершины, нужно многократно перебирать соседей текущей вершины вместе с весами рёбер до них — а именно это и возвращает adj_w[v] за один шаг.
Пример 3. Список рёбер и формат данных для алгоритма Краскала и GNN. Список рёбер — самое компактное представление, если алгоритму не важно, «чей» это список, а важен только полный перечень связей — например, чтобы отсортировать рёбра по весу.
edge_list = [(0, 1, 5), (1, 2, 3), (0, 2, 9)]
edge_list.sort(key=lambda e: e[2])
print(edge_list)
# [(1, 2, 3), (0, 1, 5), (0, 2, 9)] — отсортировано по весу для алгоритма Краскала
Этот же принцип лежит в основе того, как графовые данные передаются в библиотеки глубокого обучения на графах. PyTorch Geometric хранит структуру графа как edge_index — по сути список рёбер, только записанный в координатном (COO) формате как два параллельных массива «источники» и «приёмники», а веса или признаки рёбер — отдельным тензором edge_attr:
import torch
# те же рёбра, что в edge_list выше, но в формате PyTorch Geometric
edge_index = torch.tensor([[0, 1, 0],
[1, 2, 2]]) # источники / приёмники
edge_attr = torch.tensor([5, 3, 9]) # веса тех же рёбер
Между «списком рёбер» из классической теории алгоритмов и edge_index из современной библиотеки для GNN нет концептуальной разницы — это буквально одна и та же идея: граф как плоский перечень связей, а не как таблица или набор списков по вершинам.
Почему это важно
Для взвешенных графов выбор между матричным и списочным представлением подчиняется тем же правилам плотности, что и для невзвешенных, — просто вместо булева флага в ячейке или записи хранится числовой вес. Список рёбер как третий вариант особенно ценен там, где алгоритму нужен доступ ко всем рёбрам сразу, безотносительно того, из какой вершины они «исходят» (сортировка по весу в алгоритме Краскала, пакетная передача всей структуры графа в нейросеть за один вызов) — и именно поэтому этот формат, а не матрица и не «списки по вершинам», стал стандартом де-факто во всех современных библиотеках для глубокого обучения на графах.
Практика: 30 заданий
Базовые (задания 1–10)
Задание 1. Дан граф с 4 вершинами (0,1,2,3) и рёбрами $(0,1), (1,2), (2,3), (3,0)$. Построй его матрицу смежности.
Задание 2. Для того же графа (рёбра $(0,1), (1,2), (2,3), (3,0)$) построй список смежности.
Задание 3. Сколько байт потребуется для матрицы смежности графа из $n=500$ вершин, если каждая ячейка занимает 1 байт?
Задание 4. В списке смежности вершина $7$ имеет запись $L[7] = [2, 4, 9, 11]$. Чему равна степень вершины $7$, и за какое время эта степень определяется?
Задание 5. За какое время выполняется проверка наличия ребра $(u,v)$ в матрице смежности, и почему именно за такое время?
Задание 6. За какое время в худшем случае выполняется проверка наличия ребра $(u,v)$ в списке смежности, реализованном как обычный список (не множество)?
Задание 7. Построй матрицу смежности ориентированного графа с дугами $A\to B$, $B \to C$, $B \to D$ (вершины $A=0, B=1, C=2, D=3$).
Задание 8. По матрице смежности $\begin{bmatrix}0&1&1\\1&0&0\\0&1&0\end{bmatrix}$ определи, ориентированный это граф или нет, и обоснуй.
Задание 9. По матрице смежности неориентированного графа $\begin{bmatrix}0&1&0\\1&0&1\\0&1&0\end{bmatrix}$ определи число рёбер графа.
Задание 10. Дана матрица смежности $\begin{bmatrix}0&1&1\\1&0&0\\1&0&0\end{bmatrix}$. Построй по ней список смежности.
Средние (задания 11–20)
Задание 11. Граф содержит $n=10\,000$ вершин и $m=15\,000$ рёбер. Посчитай плотность графа $\rho = \dfrac{2m}{n(n-1)}$ и определи, разреженный он или плотный.
Задание 12. Для графа с $n=10^6$ вершин и средней степенью $30$ посчитай память для матрицы (1 бит на ячейку) и для списка (8 байт на идентификатор соседа), сравни результаты.
Задание 13. Построй взвешенную матрицу смежности для графа с рёбрами $(0,1,\text{вес }4)$, $(1,2,\text{вес }7)$, где отсутствие ребра кодируется как $\infty$, а $n=3$.
Задание 14. Построй взвешенный список смежности для того же графа из задания 13.
Задание 15. Дан список рёбер $[(2,3,8), (0,1,2), (1,2,5)]$. Отсортируй его по весу и объясни, для какого известного алгоритма такая сортировка нужна.
Задание 16. Сравни асимптотику операции «получить всех соседей вершины $v$» для матрицы смежности и списка смежности, если степень вершины $v$ равна $5$, а всего в графе $n=10^7$ вершин.
Задание 17. Сравни сложность операции «удалить ребро $(u,v)$» для матрицы смежности и для списка смежности, реализованного как обычный список (не множество).
Задание 18. Граф знаний содержит $V=5\times10^7$ сущностей и в среднем $8$ связей на сущность. Оцени, во сколько раз разреженная матрица (хранящая только реальные связи) экономнее плотной матрицы по памяти, если плотная хранит $V^2$ бит, а разреженная — по паре индексов (4 байта каждый) на каждую связь.
Задание 19. (GNN) Дана матрица смежности $A=\begin{bmatrix}0&1&0\\1&0&1\\0&1&0\end{bmatrix}$ и матрица признаков $X=\begin{bmatrix}1&2\\3&4\\5&6\end{bmatrix}$ (три вершины, по два признака). Вычисли $H=A\cdot X$ и объясни смысл результата.
Задание 20. Для графа ссылок Википедии (десятки миллионов статей, у каждой статьи в среднем несколько десятков исходящих ссылок) выбери представление — матрица или список — и обоснуй выбор через плотность графа.
Продвинутые (задания 21–30)
Задание 21. Объясни, почему реализация списка смежности через множество (set) вместо списка (list) ускоряет проверку наличия ребра до $O(1)$ в среднем, и какова цена этого ускорения.
Задание 22. Переведи список рёбер $[(0,1,2.5), (1,3,1.0), (2,1,4.0)]$ в формат edge_index и edge_attr, как это принято в PyTorch Geometric.
Задание 23. Граф знаний Wikidata содержит порядка $10^8$ сущностей и порядка $10^9$ триплетов (связей вида «субъект-отношение-объект»). Оцени среднюю степень вершины и объясни, почему матрица смежности здесь заведомо неприменима, даже если бы удалось найти достаточно памяти.
Задание 24. Сравни полный граф из $n=50$ вершин, представленный матрицей, и такой же граф, представленный списком смежности, по объёму занимаемой памяти. Какое представление предпочтительнее и почему?
Задание 25. Объясни, почему матрица смежности (а не список смежности) используется как основа для вычисления собственных значений графа (спектральный анализ, матрица Лапласиана) в некоторых методах анализа графов.
Задание 26. Объясни, почему список смежности не подходит напрямую для матричного умножения $A \cdot X$ в графовой нейросети, и как разреженная матрица (CSR/COO) решает эту проблему, сохраняя экономию памяти.
Задание 27. Предложи гибридное представление для графа, где $95\%$ вершин имеют степень $\le 5$, а $5\%$ вершин (так называемые хабы) имеют степень порядка $10^5$. Обоснуй выбор.
Задание 28. Оцени асимптотику построения матрицы смежности из списка рёбер (E рёбер, V вершин) и асимптотику построения списка смежности из того же списка рёбер. Сравни.
Задание 29. Граф — мультиграф: между вершинами $0$ и $1$ есть два разных рёбра (например, две разные дороги между городами). Почему простая матрица смежности с элементами $\{0,1\}$ не может корректно представить такой граф, и как это исправить?
Задание 30. Спроектируй представление графа для трёх сценариев: (а) граф дружбы в социальной сети с миллиардом пользователей; (б) граф из 15 городов для точного решения задачи коммивояжёра, где известны расстояния между всеми парами городов; (в) граф молекулы (около 50 атомов, каждый связан лишь с несколькими соседними атомами) как вход графовой нейросети. Обоснуй выбор для каждого.
Частые ошибки
❌ Ошибка: Считать, что список смежности всегда эффективнее матрицы смежности, независимо от графа.
✅ Правильно: Для маленьких и плотных графов матрица смежности может быть настолько же экономной по памяти, но при этом давать более быстрый доступ $O(1)$ к произвольному ребру.
💡 Почему: Выбор представления определяется плотностью конкретного графа, а не абстрактным правилом «списки лучше матриц» — у полного или почти полного графа список смежности не экономит память, а лишь усложняет доступ к произвольной паре вершин.
❌ Ошибка: Забывать, что матрица смежности неориентированного графа обязана быть симметричной, и случайно проставлять единицу только в одной из двух симметричных ячеек.
✅ Правильно: Для каждого ребра $(u,v)$ неориентированного графа нужно проставить единицу и в $A[u][v]$, и в $A[v][u]$.
💡 Почему: Если проставить единицу только в одной ячейке, обход соседей вершины $v$ через строку $A[v]$ не найдёт ребро, «записанное» лишь со стороны $u$, — граф окажется представлен некорректно и несимметрично там, где должен быть симметричен.
❌ Ошибка: Использовать матрицу смежности для графа с миллионами вершин без предварительной оценки, поместится ли она в память.
✅ Правильно: Прежде чем выбирать матричное представление для большого графа, нужно явно посчитать $n^2$ и сравнить с доступной памятью.
💡 Почему: Память растёт квадратично с числом вершин — граф, который казался «не таким уж большим» на глаз (скажем, миллион вершин), в виде матрицы требует триллион ячеек, что уже выходит за пределы памяти любого отдельного сервера.
❌ Ошибка: Путать плотность графа как долю занятых ячеек матрицы с абсолютным числом рёбер.
✅ Правильно: Плотность — это отношение реального числа рёбер к максимально возможному ($\rho = m / \binom{n}{2}$), а не само число $m$; граф с миллионом рёбер может быть как очень плотным (при малом $n$), так и крайне разреженным (при огромном $n$).
💡 Почему: Абсолютное число рёбер ничего не говорит о том, какое представление выгоднее, — решающее значение имеет именно отношение к $n^2$, а не сама величина $m$.
❌ Ошибка: Хранить список смежности как обычный список там, где приложению критично важна частая проверка наличия конкретного соседа.
✅ Правильно: Если проверка наличия конкретного ребра выполняется часто, список соседей стоит хранить как множество (set), а не как обычный список.
💡 Почему: Проверка наличия элемента в обычном списке — $O(\deg(v))$ в худшем случае, тогда как проверка в множестве — $O(1)$ в среднем; при высокой степени вершины (хабы в социальных сетях) разница становится ощутимой на практике.
❌ Ошибка: Пытаться подать граф в графовую нейросеть как плотную матрицу смежности «для простоты», не задумываясь о масштабе.
✅ Правильно: Для любого реалистичного по размеру графа (тысячи вершин и больше) нужно использовать разреженное представление (edge_index/CSR/COO), совместимое с матричными операциями библиотеки, а не строить плотную матрицу вручную.
💡 Почему: Плотная матрица для графа с десятками тысяч вершин уже требует сотен мегабайт-гигабайт, а для миллионов вершин становится физически невозможной — промышленные библиотеки для GNN по умолчанию рассчитаны на разреженный вход именно по этой причине.
Главное запомнить
✅ Матрица смежности — таблица $V \times V$, где ячейка $A[i][j]$ хранит наличие (или вес) ребра между $i$ и $j$; занимает $O(V^2)$ памяти и даёт проверку ребра за строго $O(1)$
✅ Список смежности — для каждой вершины отдельный список её соседей; занимает $O(V+E)$ памяти, обход соседей — за $O(\deg(v))$, проверка конкретного ребра — за $O(\deg(v))$ (или $O(1)$ в среднем, если соседи хранятся как множество)
✅ Выбор между матрицей и списком определяется плотностью графа $\rho = \dfrac{2m}{n(n-1)}$: для плотных графов ($\rho$ не стремится к нулю) выгодна матрица, для разреженных ($\rho \to 0$, типично для реальных графов) — список
✅ Подавляющее большинство реальных графов — социальные сети, графы знаний, молекулярные графы — разрежены: число рёбер растёт линейно, а не квадратично с числом вершин
✅ Взвешенные графы расширяют оба представления, заменяя булев флаг $0/1$ на числовой вес — в матрице это значение в ячейке (с $\infty$ для отсутствующих рёбер), в списке — пара «сосед, вес»
✅ Список рёбер — третий, самый компактный вариант представления: плоский перечень троек $(u,v,w)$, без привязки к конкретной вершине; используется в алгоритме Краскала и как основа формата edge_index в библиотеках для графовых нейросетей
✅ Разреженная матрица (CSR/COO) — практический компромисс: хранит только ненулевые элементы (как список смежности), но поддерживает стандартные матричные операции линейной алгебры
✅ Матрица смежности — буквальный математический объект в формуле графовой свёртки $H'=\sigma(AHW)$: умножение $A\cdot X$ реализует агрегацию признаков соседей, фундаментальную операцию графовых нейросетей
✅ Для маленьких плотных графов (десятки-сотни вершин, где связей много относительно $n^2$) матрица смежности — не устаревший, а зачастую оптимальный выбор
✅ Промышленные библиотеки для GNN (PyTorch Geometric, DGL) по умолчанию хранят графы в разреженном формате, а не в виде плотной матрицы, именно из-за разреженности реальных графов
Связь с темами курса
🔙 Откуда пришли: Из урока 259 — базовые понятия теории графов: вершины, рёбра, степень вершины, ориентированность, связность. Этот урок отвечает на прямой вопрос, оставшийся после предыдущего: как всё это превратить в структуру данных, с которой можно работать в коде.
🔜 Куда идём:
- Обход графов через DFS и BFS (урок 261) — оба алгоритма напрямую опираются на выбранное представление: обход соседей вершины за $O(\deg(v))$ через список смежности — стандартная основа для обоих обходов
- Топологическая сортировка (урок 262) и алгоритм Дейкстры (урок 263) — используют список смежности (в том числе взвешенный) как рабочую структуру для перебора соседей на каждом шаге
- Алгоритм Флойда–Уоршелла (урок 264) — напротив, опирается именно на взвешенную матрицу смежности, поскольку сам алгоритм по своей природе матричный (последовательно улучшает оценки расстояний между всеми парами вершин)
- Минимальное остовное дерево и алгоритм Краскала (урок 265) — напрямую используют список рёбер, отсортированный по весу, ровно в том виде, что был разобран в этом уроке
🎯 В машинном обучении: Матрица смежности — это буквальный вход графовых нейросетей (GNN): операция $A \cdot X$ реализует агрегацию признаков соседей, лежащую в основе графовых свёрточных сетей (GCN) и их многочисленных развитий (GraphSAGE, GAT и другие). Разреженное представление графа, разобранное в этом уроке как список смежности, — прямой концептуальный предок формата edge_index, на котором держится вся практическая работа с большими графами в PyTorch Geometric и аналогичных библиотеках: без понимания того, почему плотная матрица не помещается в память для реалистичного графа социальной сети или графа знаний, невозможно понять, почему промышленные системы всегда работают именно с разреженным представлением.
Интересные факты
📌 Матрица смежности графа связана с числом путей между вершинами удивительно прямым способом: элемент $A^k[i][j]$ (то есть матрица смежности, возведённая в степень $k$) равен числу путей длины ровно $k$ из вершины $i$ в вершину $j$ — это классический результат линейной алгебры на графах, который на практике используется, например, для подсчёта числа треугольников в социальной сети через след матрицы $A^3$.
📌 Граф ссылок современного интернета оценивается в триллионы страниц (вершин), но среднее число исходящих ссылок на странице — порядка десятков. Если бы Google (или любой другой поисковик) попытался представить этот граф как плотную матрицу, потребовавшийся объём памяти превысил бы суммарную ёмкость всех устройств хранения данных, когда-либо произведённых человечеством, — наглядная иллюстрация того, почему список смежности (а точнее, его распределённый по тысячам серверов вариант) не вопрос предпочтения, а единственная физически возможная альтернатива.
📌 Формат COO (coordinate format) для разреженных матриц, который сегодня лежит в основе edge_index в PyTorch Geometric, восходит к тем же самым идеям 1960–1970-х годов о компактном хранении разреженных структур, что и обычный список смежности из классических учебников по алгоритмам — современные библиотеки глубокого обучения на графах, по сути, переоткрыли и адаптировали под GPU-вычисления структуру данных полувековой давности.
📌 Число различных возможных графов на $n$ помеченных вершинах равно $2^{\binom{n}{2}}$ — уже при $n=20$ это число превышает $10^{57}$, что больше оценочного числа атомов в наблюдаемой Вселенной. Матрица смежности как раз и является тем самым компактным описанием, которое однозначно задаёт любой из этого астрономического числа графов через простую последовательность нулей и единиц.
Лайфхаки и полезные трюки
💡 Прежде чем выбирать представление для конкретного графа, посчитай его плотность одной строкой: density = 2*m / (n*(n-1)) для неориентированного графа. Если получившееся число близко к нулю (скажем, меньше $0{,}01$) — почти наверняка нужен список смежности; если оно близко к единице — матрица вполне оправданна.
💡 Перед тем как строить матрицу смежности для графа с более чем $\sim 10^4$–$10^5$ вершин, явно прикинь $n^2$ и сравни с реалистичным объёмом доступной памяти — это займёт секунды, но убережёт от попытки выделить структуру, которая в принципе не поместится в память.
💡 Если нужна и компактность списка смежности, и матричный интерфейс (например, для матричного умножения в собственной реализации GNN-слоя), используй scipy.sparse (в Python) — форматы CSR и CSC оптимальны для умножения матрицы на вектор, а COO удобен для построения структуры и последующего преобразования.
💡 Когда важна и быстрая проверка наличия ребра, и компактный перебор всех соседей, храни список смежности как dict соседа на вес ({сосед: вес}) вместо списка пар — это даёт одновременно $O(1)$-проверку конкретного соседа и $O(\deg(v))$-перебор всех соседей через .items(), без накладных расходов отдельного множества.
💡 При работе с библиотеками для GNN не пытайся вручную конвертировать список смежности в плотную матрицу «для наглядности» на реальных данных — методы вроде to_dense() в PyTorch Geometric существуют, но предназначены только для отладки на крошечных графах; на полноразмерных данных они мгновенно исчерпывают память, ровно демонстрируя проблему, разобранную в этом уроке на практике.
💡 Если сомневаешься, какое представление выбрать для конкретной задачи, задай себе один вопрос: какая операция выполняется чаще всего — проверка наличия конкретного ребра между двумя произвольными вершинами (тогда матрица или множество соседей) или перебор всех соседей заданной вершины (тогда список или разреженная матрица)? Ответ на этот единственный вопрос в большинстве практических случаев сразу указывает на правильный выбор.
Матрица смежности и список смежности — это не конкурирующие «правильный» и «неправильный» способы хранить граф, а два разных инструмента, каждый заточенный под свою задачу: один даёт мгновенный доступ ценой памяти, растущей квадратично, второй экономит память ценой чуть более медленного доступа к произвольному ребру. Ты увидел, как эта, казалось бы, инженерная деталь напрямую определяет, поместится ли граф социальной сети или графа знаний в память вообще, и как та же самая матрица смежности, которую только что научился строить руками, оказывается буквальным математическим объектом внутри формулы графовой свёрточной сети. Дальше в курсе оба представления станут рабочим инструментом: в следующем уроке про обходы графов через DFS и BFS список смежности превратится из абстрактной структуры в основу конкретных алгоритмов поиска пути, а вслед за ним — в алгоритмы кратчайших путей и минимального остовного дерева, где выбор между матрицей, списком и списком рёбер будет определять не только код, но и то, какие задачи вообще решаемы на графах реального масштаба.
Понял тему? Закрепи в боте! 🚀
Попрактикуйся на задачах и получи персональные рекомендации от AI
💪 Начать тренировку