graph

Граф

Предпосылки: базовые понятия программирования, оценка сложности в O(…), массив, хеш-таблица.

Все рассмотренные ранее структуры хранят элементы в последовательности — по позиции или по ключу. Но представим социальную сеть: 500 пользователей, каждый может быть подписан на любого другого. Нужно ответить на вопрос «подписан ли Alice на Bob?» и «на кого подписан Charlie?». Массив или хеш-таблица хранят свойства объектов, но не связи между ними. Для моделирования связей нужна другая абстракция — граф.

Определение

Граф записывают как G = (V, E): множество вершин (vertices, V) — это объекты, множество рёбер (edges, E) — связи между ними. В социальной сети вершины — пользователи, рёбра — подписки. Модель удобна, когда важно «кто с кем связан», а не только свойства самих объектов.

Виды графов

Связи в социальной сети бывают разными, и каждый тип порождает свой вид графа.

Дружба симметрична: если Alice дружит с Bob, то Bob дружит с Alice. Ребро — неупорядоченная пара {u, v}, порядок не важен. Это неориентированный граф.

Подписка асимметрична: Alice подписана на Bob, но Bob на Alice — нет. Ребро — упорядоченная пара (u, v), где (u, v) ≠ (v, u). Такие рёбра называют дугами (arcs). Это ориентированный граф (directed graph, digraph).

Теперь допустим, что у каждой связи есть «сила» — как часто пользователи взаимодействуют (лайки, комментарии). Каждому ребру сопоставляется число (вес). Это взвешенный граф (weighted graph).

Взвешенность и ориентированность — независимые свойства. Граф может быть неориентированным невзвешенным (дружба), неориентированным взвешенным (дороги с расстояниями), ориентированным невзвешенным (подписки) или ориентированным взвешенным (авиарейсы с ценами).

Путь и цикл

Вернёмся к социальной сети. Alice подписана на Bob, Bob — на Charlie. Можно ли считать, что Alice связана с Charlie через Bob? Это вопрос достижимости.

Путь — последовательность вершин (v₀, v₁, v₂, …, vₖ), где каждая соседняя пара соединена ребром. В ориентированном графе путь должен следовать направлению рёбер. В невзвешенном графе длина пути — количество рёбер, во взвешенном — сумма весов.

Цикл — путь, который начинается и заканчивается в одной вершине, а все остальные вершины в нём не повторяются (простой цикл). Alice подписана на Bob, Bob на Charlie, Charlie на Alice — цикл длины 3. Графы без циклов называются ациклическими.

Для неориентированного графа граф называется связным, если между любыми двумя вершинами существует путь. Несвязный граф распадается на отдельные компоненты, между которыми нет путей — в соцсети это изолированные группы пользователей, никак не связанные друг с другом.

Для ориентированного графа связность уточняют: граф сильно связен, если для любых двух вершин u и v существует путь из u в v и обратно. Слабо связен — если при игнорировании направлений рёбер граф становится связным. В графе подписок Alice может «дотянуться» до Bob через цепочку подписок, но обратный путь от Bob к Alice может не существовать.

Хранение графа в памяти

Граф описывает связи, но чтобы программа могла отвечать на вопросы «подписан ли Alice на Bob?» и «на кого подписан Charlie?», нужно представить его в памяти. Выбор представления определяет, какой из этих вопросов будет быстрым.

Матрица смежности (Adjacency Matrix)

Таблица V×V, где в ячейке [i][j] хранится информация о ребре между вершинами i и j.

         Alice  Bob  Charlie
Alice   [  0     1     0  ]
Bob     [  1     0     1  ]
Charlie [  0     1     0  ]

Для неориентированного графа матрица симметрична относительно главной диагонали ([i][j] = [j][i]), а диагональ заполнена нулями (если нет петель).

Проверить ребро между i и j — O(1): одно обращение к ячейке. Найти всех соседей — O(V): нужно пройти всю строку. Добавление новой вершины требует создать матрицу (V+1)×(V+1) и скопировать старые данные — O(V²). Память — O(V²).

Списки смежности (Adjacency Lists)

Для каждой вершины хранится список её соседей:

{
  Alice: [Bob],
  Bob: [Alice, Charlie],
  Charlie: [Bob]
}

Степень вершины (degree) — количество рёбер, инцидентных вершине; в списке смежности это длина списка соседей. Найти всех соседей — O(degree), проверить наличие конкретного ребра — тоже 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 ячеек × 1 байт = 100 MB. При этом средний пользователь подписан на ~150 человек, то есть рёбер ~750 000. Списки смежности: 10 000 вершин + 750 000 рёбер × 8 байт (указатель) ≈ 6 MB. Матрица тратит в 15 раз больше памяти, потому что хранит O(V²) ячеек, большинство из которых — нули. Социальная сеть — разреженный граф (рёбер значительно меньше V²), и для таких графов списки смежности почти всегда выгоднее. Матрица оправдана для плотных графов, где рёбер близко к V², и когда часто нужно проверять наличие конкретного ребра за O(1).

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

Sources

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. (graph terminology, representations, traversal complexity).

Sources

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. (graph terminology, representations, traversal complexity).