9.1   Граф¶

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

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

Рисунок 9-1   Связь между связным списком, деревом и графом

9.1.1   Распространенные типы и термины графов¶

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

• В неориентированном графе ребро означает "двустороннюю" связь между двумя вершинами, например отношение "друзья" в WeChat или QQ.
• В ориентированном графе ребро имеет направление, то есть ребра \(A \rightarrow B\) и \(A \leftarrow B\) независимы друг от друга, как, например, отношения "подписка" и "подписчик" в Weibo или Douyin.

Рисунок 9-2   Ориентированный и неориентированный графы

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

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

Рисунок 9-3   Связный и несвязный графы

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

Рисунок 9-4   Взвешенный и невзвешенный графы

Для структуры данных "граф" используются следующие распространенные термины.

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

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

Распространенные способы представления графа включают "матрицу смежности" и "список смежности". Ниже в качестве примера используется неориентированный граф.

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

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

Как показано на рисунке 9-5, пусть матрица смежности обозначается как \(M\) , а список вершин - как \(V\) ; тогда элемент матрицы \(M[i, j] = 1\) означает, что между вершинами \(V[i]\) и \(V[j]\) существует ребро, а элемент \(M[i, j] = 0\) означает, что ребра между ними нет.

Рисунок 9-5   Представление графа матрицей смежности

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

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

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

2.   Список смежности¶

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

Рисунок 9-6   Представление графа списком смежности

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

Если посмотреть на рисунок 9-6, можно заметить, что структура списка смежности очень похожа на "метод цепочек" в хеш-таблице, поэтому для оптимизации эффективности здесь можно использовать сходные идеи. Например, когда список становится слишком длинным, его можно преобразовать в AVL-дерево или красно-черное дерево, чтобы улучшить временную сложность с \(O(n)\) до \(O(\log n)\) ; можно также превратить его в хеш-таблицу и снизить сложность до \(O(1)\) .

9.1.3   Типичные применения графов¶

Как показано в таблице 9-1, многие реальные системы можно моделировать графами, а соответствующие задачи затем сводить к задачам вычислений на графах.

Таблица 9-1   Распространенные графы в реальной жизни

Оставляйте свои идеи, вопросы и предложения в комментариях