# Основные операции с графами

Основные операции с графами можно разделить на операции с ребрами и операции с вершинами. В зависимости от способа представления (матрица смежности или список смежности) реализация будет различаться.

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

Ниже приведены операции для заданного неориентированного графа с количеством вершин *n*. Способы реализации показаны на рис. 9.7.

- **Добавление или удаление ребра**: достаточно изменить соответствующее ребро в матрице смежности за время *O*(1). Поскольку граф неориентированный, необходимо обновить ребра в обоих направлениях.

- **Добавление вершины**: в конец матрицы смежности добавляется строка и столбец, которые заполняются нулями. Временная сложность равна *O*(*n*).

- **Удаление вершины**: удаляется строка и столбец из матрицы смежности. В худшем случае при удалении первой строки и столбца необходимо переместить (*n* − 1)² элементов влево вверх, что занимает время *O*(*n*²).

- **Инициализация**: передается *n* вершин, инициализируется список вершин vertices длиной *n* за время *O*(*n*). Инициализируется матрица смежности adjMat размером *n*×*n* за время *O*(*n*²).

=== "Инициализация матрицы смежности"
    ![](../assets/media/image444.jpeg)

=== "Добавление ребра"
    ![](../assets/media/image446.jpeg)

=== "Удаление ребра"
    ![](../assets/media/image448.jpeg)

=== "Добавление вершины"
    ![](../assets/media/image450.jpeg)

=== "Удаление вершины"
    ![](../assets/media/image452.jpeg)

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

```src
[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*).

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