# Графы
Граф -- это нелинейная структура данных, состоящая из вершин (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)$.
## Типичные сценарии применения графов
Многие реальные системы можно моделировать с помощью графов, а соответствующие задачи могут быть сведены к задачам вычисления на графах.
Таблица Типичные графы в реальной жизни
| | Вершина | Ребро | Задача вычисления на графе |
| ------------------- | --------------- | -------------------------------------- | ------------------------------------- |
| Социальные сети | Пользователи | Дружеские связи | Рекомендации потенциальных друзей |
| Линии метро | Станции | Связь между станциями | Рекомендации по кратчайшему маршруту |
| Солнечная система | Небесные тела | Взаимодействие гравитации между телами | Расчет орбит планет |