4.4 KiB
Основные операции с графами
Основные операции с графами можно разделить на операции с ребрами и операции с вершинами. В зависимости от способа представления (матрица смежности или список смежности) реализация будет различаться.
Реализация на основе матрицы смежности
Ниже приведены операции для заданного неориентированного графа с количеством вершин n. Способы реализации показаны на рис. 9.7.
-
Добавление или удаление ребра: достаточно изменить соответствующее ребро в матрице смежности за время O(1). Поскольку граф неориентированный, необходимо обновить ребра в обоих направлениях.
-
Добавление вершины: в конец матрицы смежности добавляется строка и столбец, которые заполняются нулями. Временная сложность равна O(n).
-
Удаление вершины: удаляется строка и столбец из матрицы смежности. В худшем случае при удалении первой строки и столбца необходимо переместить (n − 1)² элементов влево вверх, что занимает время O(n²).
-
Инициализация: передается n вершин, инициализируется список вершин vertices длиной n за время O(n). Инициализируется матрица смежности adjMat размером n×n за время O(n²).
=== "Инициализация матрицы смежности"
=== "Добавление ребра"
=== "Удаление ребра"
=== "Добавление вершины"
=== "Удаление вершины"
Ниже приведен код реализации графа на основе матрицы смежности.
[file]{graph_adjacency_matrix}-[class]{graph_adj_mat}-[func]{}
Реализация на основе списка смежности
Ниже приведены описания операций для неориентированного графа с общим количеством вершин n и ребер m. Способы реализации показаны на рис. 9.8.
-
Добавление ребра: достаточно добавить ребро в конец связного списка, соответствующего вершине за время O(1). Поскольку граф неориентированный, необходимо добавить ребра в обоих направлениях.
-
Удаление ребра: необходимо найти и удалить указанное ребро в связном списке, соответствующем вершине, за время O(m). В неориентированном графе необходимо удалить ребра в обоих направлениях.
-
Добавление вершины: добавляется связный список в список смежности, а новая вершина становится головным узлом списка. Требуется время O(1).
-
Удаление вершины: необходимо пройтись по всему списку смежности и удалить все ребра, содержащие указанную вершину. Требуется время O(n + m).
-
Инициализация: в списке смежности создается n вершин и 2m ребер. Требуется время O(n + m).
[file]{graph_adjacency_list}-[class]{graph_adj_list}-[func]{}