Граф нужно положить в код

Граф из прошлого урока — это математическая конструкция. Чтобы алгоритм мог с ним работать, граф нужно представить в виде структуры данных, лежащей в памяти. У вас есть два главных варианта: матрица смежности (adjacency matrix) и списки смежности (adjacency list). Этот урок про первый. Урок 3 — про второй. Урок 4 — про сравнение и про менее известный гибрид (CSR).

Идея матрицы простая: пронумеруйте все вершины от 0 до n-1. Заведите квадратный массив A[n][n]. Если есть ребро от i к j, поставьте A[i][j] = 1. Если нет — A[i][j] = 0.

V = {0, 1, 2, 3}
E = {(0,1), (0,2), (1,2), (2,3)}    (directed)

    0 1 2 3
  0 0 1 1 0
  1 0 0 1 0
  2 0 0 0 1
  3 0 0 0 0

Всё. Граф хранится в n^2 ячейках, каждая — один бит (или int, или float, если вы храните веса).

Код: матрица как list of lists

В Python проще всего держать матрицу как список списков:

n = 4
matrix = [[0] * n for _ in range(n)]

# добавление directed ребра u -> v
def add_edge(u: int, v: int) -> None:
    matrix[u][v] = 1

add_edge(0, 1)
add_edge(0, 2)
add_edge(1, 2)
add_edge(2, 3)

# проверка ребра
def has_edge(u: int, v: int) -> bool:
    return matrix[u][v] == 1

print(has_edge(0, 1))  # True
print(has_edge(1, 0))  # False — ребро directed, обратного нет

# обход соседей вершины u (исходящих)
def neighbors(u: int) -> list[int]:
    return [v for v in range(n) if matrix[u][v] == 1]

print(neighbors(0))  # [1, 2]

Внимание: [[0]*n] * n (без list comprehension) — это ловушка. Получите n ссылок на один и тот же список, и matrix[0][0] = 1 обновит все строки.

Для неориентированного графа нужно симметрично:

def add_undirected(u: int, v: int) -> None:
    matrix[u][v] = 1
    matrix[v][u] = 1

Матрица неориентированного графа всегда симметрична относительно диагонали (A[i][j] == A[j][i]). Это значит, что половина матрицы — дубль. Тем не менее обычно её хранят целиком; экономия на упаковке в треугольную форму обычно не оправдывает усложнение кода.

Сложность операций

Это главное, ради чего матрицу выбирают. Каждая операция здесь имеет предсказуемую сложность.

Главные характеристики:

• has_edge — O(1). Это самый быстрый способ узнать, связаны ли две вершины. Сравните с adjacency list: там придётся пройтись по списку соседей вершины u и искать v. Если у вершины 1000 соседей — это в среднем 500 сравнений. У матрицы — одно обращение к индексу.

• neighbors(u) — O(V), не O(degree). Чтобы найти соседей, нужно прочитать всю строку u, даже если у вершины мало рёбер. Если граф очень разреженный, вы будете читать в основном нули.

• Память — O(V^2). И это не «in average», а гарантированно, всегда, независимо от числа рёбер. Граф из 1000 вершин в матрице битов — 125 КБ. Граф из 100 000 вершин — 1.25 ГБ.

Числа:

Матрица растёт по V^2. Это значит: удвоили вершины — учетверили память. На 100 тысячах вершин обычная Python-матрица из int (28 байт каждый, см. модуль 3) выходит совсем катастрофически: 100k * 100k * 28 = 280 ГБ. Используют упакованные форматы (numpy.array(dtype=bool) — 1 байт на ячейку; numpy.packbits или bitarray — 1 бит).

Когда матрица оправдана: dense графы и алгебра

Несмотря на квадратичную память, матрица — не плохой выбор. Она выигрывает в трёх сценариях.

Сценарий 1. Dense graph

Если |E| близко к |V|^2 — у вас и так заполнено почти всё, экономия от sparse-представления маленькая, а O(1) на has_edge — большой бонус. Пример: completing graph (полный граф), маленький social network, distance matrix между всеми городами.

Сценарий 2. Алгебра матриц

Многие графовые алгоритмы выражаются через линейную алгебру. Если A — матрица смежности, то A^k[i][j] равно числу путей длины ровно k из i в j. A + A^2 + ... + A^(n-1) показывает все достижимые вершины. PageRank — итерационное умножение на матрицу. Spectral clustering — собственные значения матрицы.

Когда вы переходите на NumPy/SciPy, граф автоматически становится матрицей — и куча алгоритмов считается векторно, в десятки раз быстрее ручных циклов на Python.

import numpy as np

A = np.array([
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 0],
], dtype=np.int8)

# A^2: число путей длины 2 между парами вершин
A2 = A @ A
print(A2)
# [[0 0 1 1]
#  [0 0 0 1]
#  [0 0 0 0]
#  [0 0 0 0]]
# Путь длины 2 от 0 к 3: 0->1->? нет, 0->2->3 — да; от 0 к 2 — 0->1->2; и т.д.

Сценарий 3. Маленькие графы

Если |V| <= 500, разница в памяти между matrix (250 КБ) и list (примерно 10-50 КБ) несущественна. Зато O(1) lookup и простая итерация — большие плюсы. Многие учебные задачи и контест-задачи используют матрицу именно поэтому.

Когда матрица — катастрофа

Случай — когда граф большой и очень разреженный. Lineage из 100 000 таблиц с 300 000 рёбер. Матрица 100k x 100k = 10 миллиардов ячеек. Из них всего 300 тысяч единичек. Вы тратите 10 ГБ на хранение, из которых 99.997% — нули.

В adjacency list (см. урок 03) этот же граф уместится примерно в 4 МБ. Разница — в три тысячи раз.

Cache locality матрицы

Матрица из NumPy лежит в памяти как один непрерывный кусок (см. модули 02-03 про contiguous memory). Когда вы итерируете по строке, процессор подгружает cache line (64 байта = 8 значений int64) и читает их последовательно — это и есть тот самый cache hit, который ускоряет работу.

Сравните с adjacency list, где каждый список соседей — отдельный объект в куче. Чтобы пройтись по соседям, процессор скакает по разным адресам — pointer chasing, cache miss на каждом скачке.

Это значит: при равной длине кода матричный алгоритм может в 2-5 раз обгонять list-вариант на тех же данных, если они помещаются в матрицу. Когда не помещаются, list-вариант — единственный способ.

DE-кейс: связаны ли две таблицы прямо

Сценарий: у вас сервис lineage с 500 моделями. Раз в секунду кто-то запрашивает «связаны ли модели X и Y прямой зависимостью?» Если вы используете adjacency list — обход списка соседей X занимает в среднем degree/2 = 10-15 сравнений. Если матрица — это matrix[X][Y], мгновенно.

500 * 500 = 250 тысяч ячеек, 250 КБ на байт-матрице. Это копейки. Матрица — правильный выбор тут.

Тот же сервис на 50 тысячах моделей: матрица будет 2.5 ГБ. Не выбор. Adjacency list или CSR.

Попробуй сам

Постройте матрицу смежности для следующего dbt-графа из урока 01:

deps = {
    "stg_users": [],
    "stg_orders": [],
    "stg_products": [],
    "int_user_orders": ["stg_users", "stg_orders"],
    "int_order_items": ["stg_orders", "stg_products"],
    "mart_user_revenue": ["int_user_orders", "int_order_items"],
    "mart_top_products": ["int_order_items"],
}

Шаги:

1. Пронумеруйте модели от 0 до 6.
2. Создайте matrix = [[0]*7 for _ in range(7)].
3. Для каждой пары (parent, child) (где child зависит от parent), установите matrix[parent_idx][child_idx] = 1.
4. Напишите функцию direct_dependents(model: str) -> list[str], возвращающую модели, которые напрямую зависят от данной.
5. Проверьте has_edge(stg_orders, mart_user_revenue) — должно быть False (зависимость через int-слой, не прямая).

Ожидаемый результат:

• direct_dependents("stg_orders") = ["int_user_orders", "int_order_items"],
• has_edge("stg_orders", "mart_user_revenue") = False,
• Сложность операций: has_edge — O(1), direct_dependents — O(V) = O(7).

В следующем уроке мы построим тот же граф иначе — как dict[str, list[str]] — и увидим, как меняется поведение при том же API.