Графы

Граф -- это нелинейная структура данных, состоящая из вершин (vertex) и ребер (edge). Граф G можно абстрактно представить как множество вершин V и множество ребер E. Ниже приведен пример графа, содержащего 5 вершин и 7 ребер:


\begin{aligned}
V & = \{ 1, 2, 3, 4, 5 \} \newline
E & = \{ (1,2), (1,3), (1,5), (2,3), (2,4), (2,5), (4,5) \} \newline
G & = \{ V, E \} \newline
\end{aligned}

Если рассматривать вершины как узлы, а ребра как ссылки (указатели), соединяющие узлы, то граф можно рассматривать как расширенный список. Как показано на рисунке ниже, по сравнению с линейными отношениями (список) и отношениями разделения (дерево), сетевые отношения (граф) обладают большей свободой и, следовательно, являются более сложными.

Основные типы и понятия графов

В зависимости от наличия направления у ребер графы делятся на неориентированные (undirected graph) и ориентированные (directed graph), как показано на рисунке ниже.

В неориентированном графе ребро представляет собой двустороннюю связь между двумя вершинами, например дружеские отношения в социальных сетях.
В ориентированном графе ребро имеет направление. То есть ребра A \rightarrow B и A \leftarrow B независимы друг от друга, например отношения подписки--подписчики.

Если все вершины связаны, то граф называется связным (connected graph), иначе -- несвязным (disconnected graph), как показано на рисунке ниже.

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

Можно также добавить к ребрам переменную «вес», получив взвешенный граф (weighted graph), как показано на рисунке ниже. Например, в мобильных играх, таких как Honor of Kings, система рассчитывает близость между игроками на основе времени совместной игры. Такую сеть близости можно представить в виде взвешенного графа.

Со структурой данных графа связаны следующие основные понятия.

Смежность (adjacency): если между двумя вершинами существует ребро, они называются смежными. На рисунке выше вершины, смежные с вершиной 1, -- это вершины 2, 3 и 5.
Путь (path): последовательность ребер от вершины A до вершины B называется путем от A до B. На рисунке выше последовательность ребер 1-5-2-4 является путем от вершины 1 до вершины 4.
Степень (degree): количество ребер, присоединенных к вершине. Для ориентированного графа входящая степень (in-degree) показывает, сколько ребер ведет к данной вершине, а исходящая степень (out-degree) показывает, сколько ребер выходит из данной вершины.

Представление графа

Графы можно представить с помощью «матрицы смежности» и «списка смежности». Рассмотрим пример с неориентированным графом.

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

Пусть количество вершин графа равно n, матрица смежности (adjacency matrix) представляет граф в виде матрицы размером n \times n, где каждая строка (столбец) соответствует вершине, а элементы матрицы обозначают наличие ребра. Значение 1 соответствует наличию ребра между двумя вершинами, значение 0 -- отсутствию.

Обозначим матрицу смежности как M, а список вершин как V. Тогда элемент матрицы M[i, j] = 1 указывает на наличие ребра между вершинами V[i] и V[j], в противном случае элемент матрицы M[i, j] = 0.

Матрица смежности обладает следующими свойствами.

В простом графе вершина не может быть соединена с самой собой, поэтому элементы на главной диагонали матрицы смежности не имеют значения.
Для неориентированного графа ребра в обоих направлениях эквивалентны, поэтому матрица смежности симметрична относительно главной диагонали.
Заменив элементы матрицы смежности с 1 и 0 на веса ребер, можно представить взвешенный граф.

Используя матрицу смежности для представления графа, можно напрямую обращаться к элементам матрицы для получения информации о ребрах, что делает операции добавления, удаления, поиска и изменения достаточно эффективными с временной сложностью O(1). Однако пространственная сложность матрицы составляет O(n^2), что требует значительных затрат памяти.

Список смежности

Список смежности (adjacency list) представляет граф с помощью n списков, где узлы списка представляют вершины. $i$-й список соответствует вершине i и содержит все смежные вершины (вершины, соединенные с данной вершиной). На рисунке ниже показан пример графа, представленного с помощью списка смежности.

В списке смежности хранятся только существующие ребра, а общее количество ребер обычно значительно меньше n^2, что делает его более экономичным по памяти. Однако для поиска ребра в списке смежности необходимо просматривать список, что делает его менее эффективным по времени по сравнению с матрицей смежности.

Как видно из рисунка выше, структура списка смежности очень похожа на цепную адресацию в хеш-таблицах, поэтому можно использовать аналогичные методы для оптимизации эффективности. Например, если список длинный, его можно преобразовать в АВЛ-дерево или красно-черное дерево, чтобы повысить временную эффективность с O(n) до O(\log n). Также можно преобразовать список в хеш-таблицу, чтобы снизить временную сложность до O(1).

Типичные сценарии применения графов

Многие реальные системы можно моделировать с помощью графов, а соответствующие задачи могут быть сведены к задачам вычисления на графах.

Таблица Типичные графы в реальной жизни

	Вершина	Ребро	Задача вычисления на графе
Социальные сети	Пользователи	Дружеские связи	Рекомендации потенциальных друзей
Линии метро	Станции	Связь между станциями	Рекомендации по кратчайшему маршруту
Солнечная система	Небесные тела	Взаимодействие гравитации между телами	Расчет орбит планет

11 KiB Raw Permalink Blame History Unescape Escape