Матрица смежности против списков смежности

Если ты помнишь обе цены (Θ(V²) против Θ(V+E), O(1) против O(deg)) и умеешь выбирать представление по плотности и набору операций, листай до «Теперь сам».

Как думаешь, во что обойдётся таблица

Пусть в графе миллион вершин - типичный размер для дорожной сети или соцсети. Прежде чем читать дальше, прикинь: сколько памяти займёт таблица V × V, если на клетку хватит одного БИТА? И сравни с числом рёбер, которых там около десяти миллионов. Ответ объясняет, почему матрицу смежности в больших задачах не увидишь.

На что это похоже

Два способа хранить расписание встреч. Первый - большая сетка «каждый против каждого», где на пересечении стоит галочка. Ответ на вопрос «встречаются ли эти двое» мгновенный, но сетка занимает всю стену, даже если встреч всего десяток. Второй - у каждого человека свой листок со списком тех, с кем он встречается. Места ровно по числу встреч, зато чтобы ответить «встречаются ли эти двое», надо прочитать листок одного из них.

Механизм: две структуры и их цены

матрица смежности                      списки смежности
adj[u][v] = 1, если есть ребро u→v     adj[u] = [соседи вершины u]

память      Θ(V²)                      Θ(V + E)
есть ребро? O(1)                       O(deg u)   - пройти список
соседи u    O(V)   - вся строка        O(deg u)   - ровно столько, сколько есть
добавить    O(1)                       O(1)       - в конец списка
удалить     O(1)                       O(deg u)
обход всего O(V²)                      O(V + E)

В неориентированном графе ребро {u, v} записывают ДВАЖДЫ: adj[u] содержит v, а adj[v] содержит u (в матрице - симметрично относительно диагонали). Поэтому память списков - V + 2E ячеек, а сумма длин всех списков равна 2E. В ориентированном графе - по одному разу.

# списки смежности: самый обычный вид
adj = [[] for _ in range(V)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)        # только для НЕориентированного графа

# перебрать соседей вершины u - ровно deg(u) шагов
for v in adj[u]:
    ...

Полезная деталь про матрицу: если граф невзвешенный, клетке хватает одного бита, и матрицу держат битовыми словами - V²/64 машинных слов. Тогда пересечение множеств соседей (например, поиск общих друзей или треугольников) считается побитовым «И» целыми словами, по 64 вершины за операцию. Это тот случай, когда матрица выигрывает не только у списков, но и у более умных алгоритмов - за счёт железа.

Правило

Матрица смежности: память Θ(V²), проверка ребра O(1), перебор соседей O(V), обход графа O(V²). Списки смежности: память Θ(V + E), перебор соседей O(deg u), проверка ребра O(deg u), обход графа O(V + E). Разреженный граф (E ≈ V) - списки; плотный (E ≈ V²) или маленький V при частых проверках ребра - матрица. В неориентированном графе каждое ребро хранится дважды: сумма длин списков равна 2E.

Считаем вместе: миллион вершин и десять миллионов рёбер

Дорожная сеть большой страны: V = 10⁶, E = 10⁷.

матрица смежности, по биту на клетку:
    V² бит = 10¹² бит = 125 ГБ            ← не влезет в память

списки смежности, по 4 байта на номер вершины:
    2E номеров = 2·10⁷ × 4 Б = 80 МБ
    плюс V указателей/смещений: 10⁶ × 8 Б = 8 МБ
    итого ≈ 88 МБ                          ← обычный ноутбук

Разница - в полторы тысячи раз, и она не в константах, а в асимптотике: матрица платит за ОТСУТСТВУЮЩИЕ рёбра. В нашем графе заполнено 10⁷ / 10¹² = 0.001% клеток, остальные 99.999% - нули, которые честно занимают место.

Теперь плотный случай: V = 3000, граф почти полный, E ≈ 4.5·10⁶.

матрица: 3000² бит = 9·10⁶ бит ≈ 1.1 МБ
списки:  2E × 4 Б = 9·10⁶ × 4 Б = 36 МБ

Картина перевернулась: матрица в тридцать раз компактнее. Считать удобно по ОДНОМУ направлению: и матрица, и списки хранят неориентированное ребро дважды, только матрице каждое направление стоит бита, а спискам - четырёхбайтового номера, то есть 32 бит, плюс расходы структуры. Отсюда и правило выбора: дело не в «правильном» представлении, а в отношении E к V².

Разбор: когда решает не память, а набор операций

Память - не единственный довод, и вот случай, где он вообще ни при чём. Пусть V = 5000, средняя степень 100 (значит E = 5000·100/2 = 250 000), а задача: для 10 миллионов ПРОИЗВОЛЬНЫХ пар проверить, соединены ли они ребром. Матрица ответит за 10⁷ обращений в память - доли секунды. Списки пройдут список соседей: почти все случайные пары НЕ соединены, а при отсутствии элемента список читается целиком, то есть около 100 сравнений на запрос - 10⁹ операций, примерно в сто раз дольше.

Обратная ситуация: тот же граф, но задача - обойти его целиком сто раз. Матрица тратит 100 × V² = 2.5·10⁹ чтений (из них 99% - пустые клетки), списки - 100 × (V + 2E) = 100 × 505 000 ≈ 5·10⁷. Теперь примерно в пятьдесят раз быстрее списки.

Вывод, который стоит унести: прежде чем выбирать представление, выпиши, КАКИХ операций в твоей задаче больше. Три вопроса закрывают почти все случаи: (1) какова плотность E / V²; (2) чего больше - перебора соседей или проверок «есть ли ребро»; (3) меняется ли граф во время работы. Кстати, ничто не мешает держать ОБА представления сразу, если памяти хватает: списки для обходов и матрицу (или хеш-множество пар) для проверок - приём обычный и совершенно законный.

Что ломается без этого

Первое: матрица на большом графе - самая частая ошибка новичка, и она не в скорости, а в том, что программа просто не запускается: V² ячеек кончаются в памяти уже на десятках тысяч вершин. Второе: забыть симметрию в неориентированном графе - записать только adj[u].append(v). Обход пойдёт в одну сторону, и половина связей пропадёт; ошибка тихая, потому что на маленьких примерах часто «и так работает». Третье: проверять ребро линейным поиском по списку внутри цикла - и получить O(V·E) там, где ожидался O(V + E); лечится хеш-множеством пар или сортировкой списков с двоичным поиском. Четвёртое: хранить списки как list of lists из объектов при миллионах рёбер - память разлетается на служебные заголовки; в таких случаях берут один плоский массив соседей плюс массив смещений - формат CSR, compressed sparse row, «сжатые разреженные строки» (пришёл он из хранения разреженных матриц, где строка матрицы - это и есть список соседей вершины); об этом следующий урок. Пятое: удалять рёбра из списков в цикле - O(deg) на удаление, и цикл незаметно становится квадратичным.

Зачем это в работе

Выбор представления - это первое, что спрашивают на собеседовании по графам, и первое, что решает судьбу реализации. Но практический смысл шире: тот же вопрос «плотные данные или разреженные» повторяется всюду. Разреженные матрицы в численных методах хранят ровно как списки смежности (те же CSR-форматы), и по той же причине. Разреженные признаки в машинном обучении - тоже. Битовая матрица из этого урока - стандартный приём в задачах на подмножества и в анализаторах кода. И обратная сторона: если граф МАЛЕНЬКИЙ (сотни вершин), не усложняй - матрица проще, а разница в памяти неощутима. Правильный ответ почти всегда «посчитай E и V², а потом решай», и это две строки арифметики, которые экономят дни переделок.

Теперь сам

Граф веб-страниц одного сайта: V = 50 000 страниц, E = 400 000 ссылок. Главная операция - многократный обход всех ссылок (расчёт PageRank, сотни итераций). Какое представление выбрать? Посчитай память для обоих и время одной итерации.