Список рёбер, CSR и неявный граф

Если ты умеешь строить CSR за два прохода, знаешь, когда список рёбер удобнее списков смежности, и понимаешь, что такое неявный граф, листай до «Теперь сам».

Как думаешь, как хранить граф, которого не существует

Пятнашки: пятнадцать фишек в коробке 4×4, надо собрать их по порядку за наименьшее число ходов. Это графовая задача: вершина - расстановка фишек, ребро - один ход. Прежде чем читать дальше, прикинь число вершин: расстановок 16!/2 ≈ 10¹³. Ни списки, ни матрица тут не помогут - такой граф не поместится ни в какую память. Но задача решается. Вопрос: что именно мы храним, если сам граф хранить невозможно?

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

Телефонный справочник против правила набора. Справочник - это хранимый граф: все связи выписаны. Правило «код города плюс номер» - неявный граф: связь не записана нигде, но по любому номеру можно вычислить, куда он ведёт. Второй способ не занимает места вовсе и работает даже там, где выписать все номера физически нельзя.

Механизм: три формы хранения

Список рёбер. Массив пар (или троек с весом):

edges = [(0, 1, 7), (0, 2, 2), (1, 3, 4), (2, 3, 1)]
память Θ(E)   перебор соседей вершины - нельзя (только полным проходом O(E))

Годится там, где рёбра обрабатывают ЦЕЛИКОМ и в произвольном порядке: отсортировать по весу (так начинается Крускал), раздать по процессам, записать в файл. Обычно это входной формат, из которого строят что-то другое.

CSR (компактные списки смежности). Два массива вместо списка списков:

head[v]  - где в общем массиве начинаются соседи вершины v (V + 1 элемент)
dest[i]  - сам поток соседей, подряд для вершины 0, потом 1, ... (2E или E элементов)

соседи вершины v:  dest[head[v] : head[v+1]]

Строится за два прохода по списку рёбер (между ними - проход по вершинам, чтобы сложить префиксные суммы):

1) посчитать степени:        deg[u] += 1 для каждого ребра
2) префиксные суммы:         head[v+1] = head[v] + deg[v]
3) разложить рёбра по местам: pos = head.copy(); для ребра (u, v): dest[pos[u]] = v; pos[u] += 1

Зачем так: памяти ровно столько, сколько рёбер (никаких заголовков объектов и указателей), а соседи любой вершины лежат в памяти ПОДРЯД - значит читаются последовательно, и процессор успевает их подгружать. На больших графах это даёт кратное ускорение обхода при той же асимптотике. Цена - граф становится статическим: добавить ребро значит перестроить массивы.

Неявный граф. Вершины не нумеруют заранее, рёбра не хранят; есть функция:

соседи(вершина) -> список вершин

Для лабиринта это «четыре клетки вокруг, если между ними нет стены», для коня - «восемь клеток буквой Г, не вышедших за доску», для пятнашек - «передвинуть фишку рядом с дыркой». Памяти уходит столько, сколько вершин РЕАЛЬНО посетил обход, а не сколько их существует. Посещённые держат в хеш-множестве, потому что номеров у вершин нет - есть сами состояния.

Правило

Список рёбер - массив пар: память Θ(E), соседей не перебрать, зато рёбра удобно сортировать и обрабатывать целиком (входной формат, Крускал). CSR - плоские массивы head (смещения, V + 1) и dest (соседи подряд): та же асимптотика, что у списков, минимум памяти и последовательное чтение, но граф неизменяемый; строится за два прохода через степени и префиксные суммы. Неявный граф - функция соседи(v) вместо хранения; память уходит только на ПОСЕЩЁННЫЕ вершины, поэтому он работает там, где граф не помещается в память или бесконечен.

Разбор: строим CSR по шагам

Граф из четырёх вершин, рёбра неориентированные: {0,1}, {0,2}, {1,3}, {2,3}.

1. Степени. Каждое ребро добавляет единицу обоим концам: deg = [2, 2, 2, 2] (у нуля соседи 1 и 2, у единицы - 0 и 3, и так далее).
2. Префиксные суммы дают начало участка каждой вершины: head = [0, 2, 4, 6, 8] - вершина 0 занимает места 0-1, вершина 1 - места 2-3, вершина 2 - 4-5, вершина 3 - 6-7. Последний элемент (8) - общая длина, он же конец участка последней вершины; ради него массив и делают длиной V + 1.
3. Раскладка. Копируем pos = [0, 2, 4, 6] и идём по рёбрам. Ребро {0,1}: dest[0] = 1, pos[0] = 1; dest[2] = 0, pos[1] = 3. Ребро {0,2}: dest[1] = 2, pos[0] = 2; dest[4] = 0, pos[2] = 5. Ребро {1,3}: dest[3] = 3, pos[1] = 4; dest[6] = 1, pos[3] = 7. Ребро {2,3}: dest[5] = 3; dest[7] = 2. Итог: dest = [1, 2, 0, 3, 0, 3, 1, 2].

Проверим: соседи вершины 2 - это dest[head[2] : head[3]] = dest[4:6] = [0, 3]. Верно - двойка соединена с нулём и тройкой. Вся структура - два массива целых чисел, ни одного указателя, и обход for i in range(head[v], head[v+1]) читает память подряд.

Разбор: почему пятнашки решаются без хранения графа

Вернёмся к головоломке. Вершин 10¹³, но обход в ширину от начальной расстановки посещает не все - он идёт по уровням и останавливается, как только нашёл цель. Хранить нужно только ГРАНИЦУ поиска (очередь) и множество посещённых. Для задач, решаемых за 20-30 ходов, это миллионы состояний, а не десять триллионов - помещается.

Механика такая: вершина - это само состояние (кортеж из шестнадцати чисел или упакованное в одно 64-битное целое), соседи(состояние) двигает дырку в четыре стороны и возвращает новые состояния, посещённые лежат в хеш-множестве. Никакой нумерации вершин, никаких списков смежности - граф раскрывается по мере обхода, откуда и название: его называют ещё графом, заданным НЕЯВНО, или поиском в пространстве состояний.

Этот приём переносится на огромный класс задач: разбор ходов в игре, поиск пути в игровом мире по клеткам, подбор последовательности операций (кубик Рубика, переливания, переключение ламп), проверка достижимости состояний протокола или конечного автоматаРазбирается в разделе 21, глава «Конечные автоматы и регулярные языки»: Конечный автомат: вычисление, которому хватает одного состояния. Общая примета: «состояний много, но правило перехода простое». И общее ограничение: неявный граф не позволяет заранее узнать V и E, поэтому оценки пишут через число ДОСТИЖИМЫХ состояний, а память ограничивают сознательно - иначе множество посещённых съест всё.

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

Первое: пытаться обходить граф прямо по списку рёбер - каждый шаг придётся искать нужные рёбра полным проходом, и O(V + E) превращается в O(V·E). Список рёбер сначала переводят в списки смежности или CSR. Второе: строить CSR и потом добавлять рёбра - массивы придётся перестраивать целиком; для меняющегося графа берут обычные списки. Третье: в неявном графе забыть множество посещённых - обход зациклится, потому что состояния повторяются (в лабиринте можно ходить туда-сюда бесконечно). Четвёртое: хранить в множестве посещённых сами объекты-состояния без нормализации - два одинаковых состояния, записанных по-разному, будут считаться разными, и обход раздуется. Пятое, из практики: забыть, что вершины в реальных данных - это строки (имена пакетов, URL, идентификаторы), и алгоритмы работают с номерами. Отображение «имя → номер» делают словарём один раз на входе, а обратное - массивом; путаница здесь даёт неверные ответы на верном алгоритме.

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

CSR - стандарт де-факто в библиотеках для больших графов и разреженных матриц (SciPy, графовые движки, GPU-вычисления): именно в этом виде граф живёт, когда вершин миллиарды. Список рёбер - формат обмена: так граф приходит из базы, из лога, из файла, так его отдают алгоритмам, которым нужны рёбра целиком и по порядку веса. Неявный граф - то, чем ты будешь пользоваться чаще всего, даже не называя это графом: любой поиск по состояниям, любой обход дерева каталогов, любой «дойти отсюда туда по правилам» - это он. И общий навык, который стоит унести: представление выбирают ПОД ОПЕРАЦИИ, а не под красоту, и его нормально менять по ходу - прочитать граф списком рёбер, построить CSR за два прохода, обойти, выбросить.

Теперь сам

Ориентированный граф задан списком рёбер: (0,2), (0,3), (1,0), (2,3), (3,1). Построй CSR (массивы head и dest) и скажи, кто соседи вершины 0 и вершины 3.