Граф
Предпосылки: базовые понятия программирования, оценка сложности в O(…), указатели и ссылки, базовое чтение Ruby (методы, массивы и хеши), массив, хеш-таблица.
← Clock-Sweep | Дерево →
Все рассмотренные ранее структуры хранят элементы в последовательности — по позиции или по ключу. Но представим социальную сеть: 500 пользователей, каждый может быть подписан на любого другого. Нужно ответить на вопрос «подписан ли Alice на Bob?» и «на кого подписан Charlie?». Массив или хеш-таблица хранят свойства объектов, но не связи между ними. Для моделирования связей нужна другая абстракция — граф.
Вершины и рёбра
Граф состоит из двух множеств: вершины (объекты) и рёбра (связи между ними). В социальной сети вершины — пользователи, рёбра — подписки. Дальше количество вершин обозначается V, количество рёбер — E: оценки операций и памяти удобнее записывать через эти два числа. Модель работает там, где важно «кто с кем связан», а не только свойства самих объектов.
Виды графов
Связи в социальной сети бывают разными, и каждый тип порождает свой вид графа.
Дружба симметрична: если Alice дружит с Bob, то Bob дружит с Alice. Ребро тут — просто пара вершин без направления: «Alice — Bob» и «Bob — Alice» означают одно и то же. Это неориентированный граф.
Подписка асимметрична: Alice подписана на Bob, но Bob на Alice — нет. Здесь у ребра есть направление: «от Alice к Bob» и «от Bob к Alice» — разные связи, и одна может существовать без другой. Это ориентированный граф.
Теперь допустим, что у каждой связи есть «сила» — как часто пользователи взаимодействуют (лайки, комментарии). Каждому ребру сопоставляется число — вес. Это взвешенный граф.
Взвешенность и ориентированность — независимые свойства. Граф может быть неориентированным невзвешенным (дружба), неориентированным взвешенным (дороги с расстояниями), ориентированным невзвешенным (подписки) или ориентированным взвешенным (авиарейсы с ценами).
Путь, цикл, связность
Вернёмся к социальной сети. Alice подписана на Bob, Bob — на Charlie. Можно ли считать, что Alice связана с Charlie через Bob? Связь между несоседними вершинами — это путь: цепочка вершин, в которой каждая соседняя пара соединена ребром (Alice → Bob → Charlie). В ориентированном графе путь идёт по направлению рёбер, иначе по подпискам до Charlie не добраться.
Путь может вернуться в начало: Alice подписана на Bob, Bob на Charlie, Charlie на Alice — цепочка замкнулась. Замкнутый путь, не проходящий дважды через одну вершину, называется циклом. Граф без циклов называется ациклическим — в нём, начав из любой вершины и идя по рёбрам, нельзя вернуться к ней же.
Если между любыми двумя вершинами существует путь, граф называется связным. Несвязный граф распадается на изолированные части, между которыми путей нет, — в соцсети это группы пользователей, никак не соединённые друг с другом.
Эти понятия — путь, цикл, связность — нужны, чтобы решить, как хранить граф, и ниже они работают именно для этого. Сам обход графа (как фактически найти путь или обнаружить цикл, не зациклившись) — отдельная тема: для ориентированных графов связность дополнительно делят на сильную и слабую, и оба случая разбираются вместе с алгоритмами обхода.
Хранение графа в памяти
Граф описывает связи, но чтобы программа могла отвечать на вопросы «подписан ли Alice на Bob?» и «на кого подписан Charlie?», нужно представить его в памяти. Выбор представления определяет, какой из этих вопросов будет быстрым.
Матрица смежности
Первый способ — завести квадратную таблицу, по строке и столбцу на каждую вершину. Если вершин V штук, таблица имеет размер V×V. В ячейке на пересечении строки i и столбца j стоит 1, если ребро между вершинами i и j есть, и 0, если нет (для взвешенного графа вместо 1 хранится вес).
Alice Bob Charlie
Alice [ 0 1 0 ]
Bob [ 1 0 1 ]
Charlie [ 0 1 0 ]В неориентированном графе ребро «Alice — Bob» — то же, что «Bob — Alice», поэтому таблица зеркальна: ячейка [i][j] равна [j][i]. Диагональ ([i][i]) — это ребро вершины к самой себе (петля); в социальной сети их нет, поэтому диагональ нулевая.
Где такая таблица сильна, а где слаба, видно прямо по ней. Проверить ребро между i и j — заглянуть в одну ячейку, O(1). Добавить или удалить ребро — переписать одну ячейку (0 ↔ 1), тоже O(1). Найти всех соседей вершины — пройти всю её строку из V ячеек, в большинстве из которых ноль, O(V). Добавить вершину — это лишняя строка и столбец, то есть новая таблица (V+1)×(V+1) с копированием старой, O(V²). Память — O(V²): ячейка хранится для каждой возможной пары вершин, даже если ребра нет.
Списки смежности
Второй способ — для каждой вершины хранить только список тех, с кем она реально соединена (её соседей):
{
Alice: [Bob],
Bob: [Alice, Charlie],
Charlie: [Bob],
}Степень вершины (degree) — сколько рёбер из неё выходит; в этом представлении это просто длина её списка соседей. Найти всех соседей — пройти список, O(degree). Проверить конкретное ребро — тоже O(degree): чтобы узнать, есть ли Bob среди соседей Alice, список приходится просмотреть. Добавить ребро — дописать вершину в список, O(1); удалить — найти и убрать, O(degree). Память — O(V + E): хранится по записи на вершину и по записи на каждое существующее ребро, нулей нет.
Выбор представления
| Критерий | Матрица смежности | Списки смежности |
|---|---|---|
| Память | O(V²) | O(V + E) |
| Проверить ребро | O(1) | O(degree) |
| Найти соседей | O(V) | O(degree) |
| Добавить ребро | O(1) | O(1) |
| Удалить ребро | O(1) | O(degree) |
| Добавить вершину | O(V²) | O(1) |
Разница в памяти ощутима на реальных числах. Социальная сеть с 10 000 пользователей. Матрица: 10 000 строк × 10 000 столбцов = 100 млн ячеек; если в ячейке хранится один байт (0 или 1), это 100 MB. Теперь посчитаем рёбра: пусть в среднем у пользователя 150 связей (дружба — связь неориентированная, так что одно ребро соединяет двух людей). Тогда рёбер около 10 000 × 150 / 2 = 750 000. В списках смежности неориентированное ребро хранится дважды — по записи в списке соседей у каждого из двух концов, чтобы соседей можно было найти от любой вершины; запись — это ссылка на соседнюю вершину, порядка 8 байт. Итого ≈ 750 000 × 2 × 8 байт ≈ 12 MB (плюс по списку на каждую из 10 000 вершин — это уже мелочь на фоне рёбер). Матрица тратит примерно в 8 раз больше, потому что держит O(V²) ячеек, и при таком числе связей подавляющее большинство — нули.
Социальная сеть — разреженный граф: рёбер значительно меньше V². Для таких графов списки смежности почти всегда выгоднее по памяти. Матрица оправдана для плотных графов, где рёбер близко к V², и там, где постоянно нужна проверка конкретного ребра за O(1).
Граф — самая общая из структур связей: рёбра можно проводить как угодно, циклы разрешены. Если же из связного графа убрать рёбра так, чтобы между любыми двумя вершинами остался ровно один путь (ни одного цикла, ни одной лишней связи), получается более строгая форма — дерево.
Sources
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. (graph terminology, representations, traversal complexity).
← Clock-Sweep | Дерево →