Базовые операции графа

Базовые операции графа можно разделить на операции над «ребрами» и операции над «вершинами». При двух способах представления, «матрице смежности» и «списке смежности», реализация этих операций различается.

Реализация на основе матрицы смежности

Пусть дан неориентированный граф с числом вершин \(n\) . Тогда способы реализации различных операций показаны на рисунке ниже.

• Добавление или удаление ребра: достаточно изменить соответствующее ребро в матрице смежности, что требует \(O(1)\) времени. Поскольку граф неориентированный, необходимо одновременно обновить ребра в обоих направлениях.
• Добавление вершины: в конец матрицы смежности добавляется строка и столбец, полностью заполненные нулями. Это требует \(O(n)\) времени.
• Удаление вершины: из матрицы смежности удаляется строка и столбец. При удалении первой строки и первого столбца достигается худший случай, когда требуется «сдвинуть влево вверх» \((n-1)^2\) элементов, поэтому используется \(O(n^2)\) времени.
• Инициализация: передаются \(n\) вершин, затем инициализируется список вершин vertices длины \(n\) , что требует \(O(n)\) времени. После этого инициализируется матрица смежности adjMat размера \(n \times n\) , что требует \(O(n^2)\) времени.

<1><2><3><4><5>

Ниже приведен код реализации графа на основе матрицы смежности:

[file]{graph_adjacency_matrix}-[class]{graph_adj_mat}-[func]{}

Реализация на основе списка смежности

Пусть неориентированный граф содержит в сумме \(n\) вершин и \(m\) ребер. Тогда различные операции можно реализовать способом, показанным на рисунке ниже.

• Добавление ребра: достаточно добавить ребро в конец списка, соответствующего вершине. Это требует \(O(1)\) времени. Поскольку граф неориентированный, необходимо одновременно добавить ребра в обоих направлениях.
• Удаление ребра: нужно найти и удалить указанное ребро в списке, соответствующем вершине. Это требует \(O(m)\) времени. В неориентированном графе необходимо удалить ребра в обоих направлениях.
• Добавление вершины: в список смежности добавляется еще один список, а новая вершина становится его головным узлом. Это требует \(O(1)\) времени.
• Удаление вершины: требуется пройти по всему списку смежности и удалить все ребра, содержащие указанную вершину. Это требует \(O(n + m)\) времени.
• Инициализация: в списке смежности создаются \(n\) вершин и \(2m\) ребер. Это требует \(O(n + m)\) времени.

<1><2><3><4><5>

Ниже приведен код списка смежности. По сравнению с тем, что показано на рисунке выше, реальная реализация имеет следующие отличия.

• Чтобы упростить добавление и удаление вершин, а также сделать код проще, мы используем список, то есть динамический массив, вместо связного списка.
• Для хранения списка смежности используется хеш-таблица, где key - это экземпляр вершины, а value - список смежных вершин данной вершины.

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

[file]{graph_adjacency_list}-[class]{graph_adj_list}-[func]{}

Сравнение эффективности

Пусть в графе имеется \(n\) вершин и \(m\) ребер. В таблице ниже сравниваются временная и пространственная эффективность матрицы смежности и списка смежности. Обратите внимание: список смежности (связный список) соответствует реализации из этой статьи, а список смежности (хеш-таблица) означает вариант, в котором все списки заменены хеш-таблицами.

Таблица   Сравнение матрицы смежности и списка смежности

	Матрица смежности	Список смежности (связный список)	Список смежности (хеш-таблица)
Проверка смежности	\(O(1)\)	\(O(n)\)	\(O(1)\)
Добавление ребра	\(O(1)\)	\(O(1)\)	\(O(1)\)
Удаление ребра	\(O(1)\)	\(O(n)\)	\(O(1)\)
Добавление вершины	\(O(n)\)	\(O(1)\)	\(O(1)\)
Удаление вершины	\(O(n^2)\)	\(O(n + m)\)	\(O(n)\)
Занимаемая память	\(O(n^2)\)	\(O(n + m)\)	\(O(n + m)\)

Если судить только по данным в таблице выше, может показаться, что список смежности на основе хеш-таблицы является лучшим и по времени, и по памяти. Но на практике операции над ребрами в матрице смежности обычно выполняются быстрее, потому что там нужен лишь один доступ к массиву или одно присваивание. В целом матрица смежности воплощает принцип «обмена пространства на время», а список смежности - принцип «обмена времени на пространство».