9.1   Граф¶

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

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

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

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

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

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

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

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

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

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

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

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

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

• Смежность (adjacency): если между двумя вершинами существует ребро, то такие вершины называются смежными. На рисунке 9-4 с вершиной 1 смежны вершины 2, 3 и 5.
• Путь (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   Распространенные графы в реальной жизни

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