# Графы

![](ru/docs/assets/media/image430.jpeg){width="3.5416732283464567in" height="4.583333333333333in"}

#### графы

> *Граф --* это нелинейная структура данных, состоящая из вершин и ребер. Граф *G* можно абстрактно представить как множество *вершин V* и множество *ребер E*. Ниже приведен пример графа, содержащего 5 вершин и 7 ребер:
>
> *V* = {1, 2, 3, 4, 5}
>
> *E* = {(1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 5), (4, 5)}
>
> *G* = {*V*, *E*}.
>
> Если рассматривать вершины как узлы, а ребра как ссылки (указатели), соединяющие узлы, то граф можно рассматривать как расширенный спи- сок. **По сравнению с линейными отношениями (список) и отношени- ями разделения (дерево), сетевые отношения (граф) обладают боль- шей свободой** и, следовательно, являются более сложными, как показано на рис. 9.1.

![](ru/docs/assets/media/image432.jpeg)

> **Рис. 9.1.** Связь между списком, деревом и графом

1.  **Основные типы и понятия графов**

> В зависимости от наличия направления у ребер графы делятся на неориенти- рованные и ориентированные, как показано на рис. 9.2.

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

- В ориентированном графе ребро имеет направление. То есть ребра *A* → *B* и *A* ← *B* независимы друг от друга, например отношения подписки--под- писчики.

> ![](ru/docs/assets/media/image434.jpeg)
>
> **Рис. 9.2.** Ориентированный и неориентированный графы
>
> Если все вершины связаны, то граф называется связным, иначе -- несвяз- ным, как показано на рис. 9.3.
>
> В связном графе из любой вершины можно достичь любой другой вершины. В несвязном графе существуют по крайней мере две вершины, между кото-
>
> рыми нет пути.

![](ru/docs/assets/media/image436.jpeg)

> **Рис. 9.3.** Связный и несвязный графы
>
> Можно также добавить к ребрам переменную «вес», получив взвешенный граф, как показано на рис. 9.4. Например, в мобильных играх, таких как Honor of Kings, система рассчитывает близость между игроками на основе времени совместной игры. Такую сеть близости можно представить в виде взвешенного графа.
>
> Со структурой данных графа связаны следующие основные понятия.

- **Смежность**: если между двумя вершинами существует ребро, они на- зываются смежными. На рис. 9.4 вершины, смежные с вершиной 1, -- это вершины 2, 3 и 5.

- **Путь**: последовательность ребер от вершины *A* до вершины *B* называет- ся путем от *A* до *B*. На рис. 9.4 последовательность ребер 1-5-2-4 является путем от вершины 1 до вершины 4.

- **Степень**: количество ребер, присоединенных к вершине. Для ориен- тированного графа входящая степень показывает, сколько ребер ведет к данной вершине, а исходящая степень показывает, сколько ребер вы- ходит из данной вершины.

> ![](ru/docs/assets/media/image438.jpeg)
>
> **Рис. 9.4.** Взвешенный и невзвешенный графы

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

> Графы можно представить с помощью матрицы смежности и списка смежно- сти. Рассмотрим пример с неориентированным графом.

##### Матрица смежности

> Пусть количество вершин графа равно *n*, *матрица смежности* представля- ет граф в виде матрицы размером *n*×*n*, где каждая строка (столбец) соот- ветствует вершине, а элементы матрицы обозначают наличие ребра. Зна- чение 1 соответствует наличию ребра между двумя вершинами, значение 0 -- отсутствию.
>
> Обозначим матрицу смежности как *M*, а список вершин как *V*. Тогда элемент матрицы *M*\[*i*, *j*\] = 1 указывает на наличие ребра между вершинами *V*\[*i*\] и *V*\[*j*\], в противном случае элемент матрицы *M*\[*i*, *j*\] = 0, см. рис. 9.5.

![](ru/docs/assets/media/image440.jpeg)

> **Рис. 9.5.** Представление графа с помощью матрицы смежности
>
> Матрица смежности обладает следующими свойствами.

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

- Для неориентированного графа ребра в обоих направлениях эквива- лентны, поэтому матрица смежности симметрична относительно глав- ной диагонали.

- Заменив элементы матрицы смежности с 1 и 0 на веса ребер, можно представить взвешенный граф.

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

##### Список смежности

> *Список смежности* представляет граф с помощью *n* списков, где узлы списка представляют вершины. *i*-й список соответствует вершине *i* и содержит все смежные вершины (вершины, соединенные с данной вершиной). На рис. 9.6 показан пример графа, представленного с помощью списка смежности.

![](ru/docs/assets/media/image442.jpeg)

> **Рис. 9.6.** Представление графа с помощью списка смежности
>
> В списке смежности хранятся только существующие ребра, а общее количе- ство ребер обычно значительно меньше *n*2, что делает его более экономичным по памяти. Однако для поиска ребра в списке смежности необходимо просма- тривать список, что делает его менее эффективным по времени по сравнению с матрицей смежности.

###### Как видно из рис. 9.6, структура списка смежности очень похожа на цепную адресацию в хеш-таблицах, поэтому можно использовать ана-

> **логичные методы для оптимизации эффективности**. Например, если список длинный, его можно преобразовать в АВЛ-дерево или красно-черное дерево, чтобы повысить временную эффективность с *O*(*n*) до *O*(log *n*). Так- же можно преобразовать список в хеш-таблицу, чтобы снизить временную сложность до *O*(1).

### Типичные сценарии применения графов

> Многие реальные системы можно моделировать с помощью графов, а соответ- ствующие задачи могут быть сведены к задачам вычисления на графах, см. табл. 9.1.

+---------------------+-----------------+-------------------------+------------------------------------------+
|                     | > **Вершина**   | > **Ребро**             | > **Задача вычисления на графе**         |
+=====================+=================+=========================+==========================================+
| > Социальные сети   | > Пользователи  | > Дружеские связи       | > Рекомендации потенци- альных друзей    |
+---------------------+-----------------+-------------------------+------------------------------------------+
| > Линии метро       | > Станции       | > Связь между станциями | > Рекомендации по крат- чайшему маршруту |
+---------------------+-----------------+-------------------------+------------------------------------------+
| > Солнечная система | > Небесные тела | > Взаимодействие грави- | > Расчет орбит планет                    |
+---------------------+-----------------+-------------------------+------------------------------------------+

> тации между телами

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

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

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

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

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

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

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

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

> ![](ru/docs/assets/media/image444.jpeg)

![](ru/docs/assets/media/image446.jpeg)![](ru/docs/assets/media/image448.jpeg)

> **Рис. 9.7.** Инициализация матрицы смежности, добавление и удаление ребер и вершин. Шаги 1--3
>
> ![](ru/docs/assets/media/image450.jpeg)

![](ru/docs/assets/media/image452.jpeg)

> **Рис. 9.7.** *Окончание*. Шаги 4--5
>
> Ниже приведен код реализации графа на основе матрицы смежности.
>
> \# === File: graph_adjacency_matrix.py === class GraphAdjMat:
>
> \"\"\" Класс неориентированного графа на основе матрицы смежности.\"\"\"
>
> def init (self, vertices: list\[int\], edges: list\[list\[int\]\]): \"\"\" Конструктор.\"\"\"
>
> \# Список вершин, элемент представляет \"значение вершины\", индекс пред-
>
> ставляет \"индекс вершины\".
>
> self.vertices: list\[int\] = \[\]
>
> \# Матрица смежности, индексы строк и столбцов соответствуют \# \"индексу вершины\".
>
> self.adj_mat: list\[list\[int\]\] = \[\]
>
> \# Добавление вершин. for val in vertices:
>
> self.add_vertex(val) \# Добавление ребер.
>
> \# Обратите внимание: элементы edges представляют индексы вершин, \# т. е. соответствуют индексам элементов vertices.
>
> for e in edges: self.add_edge(e\[0\], e\[1\])
>
> def size(self) -\> int:
>
> \"\"\" Получение количества вершин.\"\"\" return len(self.vertices)
>
> def add_vertex(self, val: int): \"\"\" Добавление вершины.\"\"\" n = self.size()
>
> \# Добавление нового значения вершины в список вершин.
>
> self.vertices.append(val)
>
> \# Добавление строки в матрицу смежности. new_row = \[0\] \* n self.adj_mat.append(new_row)
>
> \# Добавление столбца в матрицу смежности.
>
> for row in self.adj_mat: row.append(0)
>
> def remove_vertex(self, index: int): \"\"\" Удаление вершины.\"\"\"
>
> if index \>= self.size(): raise IndexError()
>
> \# Удаление вершины с индексом index из списка вершин.
>
> self.vertices.pop(index)
>
> \# Удаление строки с индексом index из матрицы смежности. self.adj_mat.pop(index)
>
> \# Удаление столбца с индексом index из матрицы смежности.
>
> for row in self.adj_mat: row.pop(index)
>
> def add_edge(self, i: int, j: int): \"\"\" Добавление ребра.\"\"\"
>
> \# Параметры i и j соответствуют индексам элементов vertices. \# Обработка выхода за границы индексов и равенства.
>
> if i \< 0 or j \< 0 or i \>= self.size() or j \>= self.size() or i == j: raise IndexError()
>
> \# В неориентированном графе матрица смежности симметрична
>
> \# относительно главной диагонали, т. е. (i, j) == (j, i). self.adj_mat\[i\]\[j\] = 1
>
> self.adj_mat\[j\]\[i\] = 1
>
> def remove_edge(self, i: int, j: int): \"\"\" Удаление ребра.\"\"\"
>
> \# Параметры i и j соответствуют индексам элементов vertices.
>
> \# Обработка выхода за границы индексов и равенства.
>
> if i \< 0 or j \< 0 or i \>= self.size() or j \>= self.size() or i == j: raise IndexError()
>
> self.adj_mat\[i\]\[j\] = 0
>
> self.adj_mat\[j\]\[i\] = 0
>
> def print(self):
>
> \"\"\" Печать матрицы смежности.\"\"\"
>
> print(\" Список вершин =\", self.vertices) print(\" Матрица смежности =\") print_matrix(self.adj_mat)

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

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

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

- **Удаление ребра**: необходимо найти и удалить указанное ребро в связ- ном списке, соответствующем вершине, за время *O*(*m*). В неориентиро- ванном графе необходимо удалить ребра в обоих направлениях.

- **Добавление вершины**: добавляется связный список в список смеж- ности, а новая вершина становится головным узлом списка. Требуется время *O*(1).

- **Удаление вершины**: необходимо пройтись по всему списку смежности и удалить все ребра, содержащие указанную вершину. Требуется время *O*(*n* + *m*).

- **Инициализация**: в списке смежности создается *n* вершин и 2*m* ребер за время O(*n* + *m*).

![](ru/docs/assets/media/image454.jpeg)

> **Рис. 9.8.** Инициализация списка смежности, добавление и удаление ребер и вершин.
>
> Шаг 1
>
> ![](ru/docs/assets/media/image456.jpeg)

![](ru/docs/assets/media/image458.jpeg)![](ru/docs/assets/media/image460.jpeg)

> **Рис. 9.8.** *Продолжение*. Шаг 2--4
>
> ![](ru/docs/assets/media/image462.jpeg)
>
> **Рис. 9.8.** *Окончание*. Шаг 5
>
> Ниже приведен код реализации списка смежности. По сравнению с рис. 9.8 код имеет следующие отличия:

- для удобства добавления и удаления вершин, а также упрощения кода вместо связного списка используется список (динамический массив);

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

> Кроме того, в списке смежности используется класс Vertex для представле- ния вершин. Это сделано потому, что если, как в случае с матрицей смежности, использовать индексы списка для различения различных вершин, то при уда- лении вершины с индексом *i* необходимо пройтись по всему списку смежно- сти и уменьшить на 1 все индексы, большие *i*, что крайне неэффективно. Если же каждая вершина является уникальным экземпляром класса Vertex, то после удаления одной вершины не требуется изменять другие вершины.
>
> \# === File: graph_adjacency_list.py === class GraphAdjList:
>
> \"\"\" Класс неориентированного графа на основе списка смежности.\"\"\"
>
> def init (self, edges: list\[list\[Vertex\]\]): \"\"\" Конструктор.\"\"\"
>
> \# Список смежности, ключ: вершина, значение: все смежные вершины данной
>
> вершины.
>
> self.adj_list = dict\[Vertex, list\[Vertex\]\]() \# Добавление всех вершин и ребер.
>
> for edge in edges: self.add_vertex(edge\[0\]) self.add_vertex(edge\[1\]) self.add_edge(edge\[0\], edge\[1\])
>
> def size(self) -\> int:
>
> \"\"\" Получение количества вершин.\"\"\" return len(self.adj_list)
>
> def add_edge(self, vet1: Vertex, vet2: Vertex): \"\"\" Добавление ребра.\"\"\"
>
> if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2: raise ValueError()
>
> \# Добавление ребра vet1 - vet2 self.adj_list\[vet1\].append(vet2) self.adj_list\[vet2\].append(vet1)
>
> def remove_edge(self, vet1: Vertex, vet2: Vertex): \"\"\" Удаление ребра.\"\"\"
>
> if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2: raise ValueError()
>
> \# Удаление ребра vet1 - vet2. self.adj_list\[vet1\].remove(vet2) self.adj_list\[vet2\].remove(vet1)
>
> def add_vertex(self, vet: Vertex): \"\"\" Добавление вершины.\"\"\"
>
> if vet in self.adj_list: return
>
> \# В списке смежности добавляется новый список. self.adj_list\[vet\] = \[\]
>
> def remove_vertex(self, vet: Vertex): \"\"\" Удаление вершины.\"\"\"
>
> if vet not in self.adj_list: raise ValueError()
>
> \# В списке смежности удаляется список, соответствующий вершине vet. self.adj_list.pop(vet)
>
> \# Обход списков других вершин, удаление всех ребер, содержащих vet. for vertex in self.adj_list:
>
> if vet in self.adj_list\[vertex\]: self.adj_list\[vertex\].remove(vet)
>
> def print(self):
>
> \"\"\" Печать списка смежности.\"\"\" print(\" Список смежности =\") for vertex in self.adj_list:
>
> tmp = \[v.val for v in self.adj_list\[vertex\]\] print(f\"{vertex.val}: {tmp},\")

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

> Пусть дан граф с *n* вершинами и *m* ребрами. В табл. 9.2 приведено сравне- ние временной и пространственной сложности матрицы смежности и списка смежности.
>
> **Таблица 9.2.** Сравнение матрицы и списка смежности

+---------------------------------------------------------------------------------------------------------------+
| > **Операция Матрица Список смежности Список смежности смежности (связный список) (хеш-таблица)**             |
+===========================+===========================+===========================+===========================+
| > Проверка смежности      | > *O*(1)                  | > *O*(*m*)                | > *O*(1)                  |
+---------------------------+---------------------------+---------------------------+---------------------------+
| > Добавление ребра        | > *O*(1)                  | > *O*(1)                  | > *O*(1)                  |
+---------------------------+---------------------------+---------------------------+---------------------------+
| > Удаление ребра          | > *O*(1)                  | > *O*(*m*)                | > *O*(1)                  |
+---------------------------+---------------------------+---------------------------+---------------------------+
| > Добавление вершины      | > *O*(*n*)                | > *O*(1)                  | > *O*(1)                  |
+---------------------------+---------------------------+---------------------------+---------------------------+
| > Удаление вершины        | > *O*(*n*²)               | > *O*(*n* + *m*)          | > *O*(*n*)                |
+---------------------------+---------------------------+---------------------------+---------------------------+
| > Занимаемое пространство | > *O*(*n*²)               | > *O*(*n* + *m*)          | > *O*(*n* + *m*)          |
+---------------------------+---------------------------+---------------------------+---------------------------+

> Из табл. 9.2 видно, что временная и пространственная эффективность спи- ска смежности (хеш-таблица) наиболее оптимальна. Однако на практике опе- рации с ребрами в матрице смежности более эффективны, так как требуют лишь одного доступа или присвоения в массиве. В целом матрица смежности реализует принцип обмена пространства на время, тогда как список смежно- сти -- обмена времени на пространство.

#### Обход графа

> Дерево представляет собой отношение «один ко многим», тогда как граф обла- дает большей степенью свободы и может представлять произвольные отноше- ния «многие ко многим». Таким образом, **дерево можно рассматривать как частный случай графа**. Очевидно, что операции обхода дерева также являют- ся частным случаем обхода графа.
>
> И графы, и деревья требуют применения алгоритмов поиска для реализации операций обхода. Способы обхода графа можно разделить на два типа: обход в ширину и обход в глубину.

### Обход в ширину

> **Обход в ширину (BFS)** -- **это метод обхода от ближнего к дальнему**, **начи- ная с определенного узла**, **с посещением в первую очередь ближайших вершин с постепенным расширением наружу**. Начиная с левого верхнего угла, сначала обходятся все смежные вершины текущей вершины, затем все смежные вершины следующей вершины и т. д., пока не будут посещены все вершины, как показано на рис. 9.9.
>
> ![](ru/docs/assets/media/image464.jpeg)
>
> **Рис. 9.9.** Обход графа в ширину

##### Реализация алгоритма

> Обход в ширину обычно реализуется с помощью очереди, код реализации при- веден ниже. Очередь обладает свойством «первый пришел -- первый вышел», что соответствует идее обхода в ширину «от ближнего к дальнему». Алгоритм следующий:

1)  добавить начальную вершину обхода startVet в очередь и начать цикл;

2)  на каждой итерации цикла извлекать вершину из головы очереди и за- писывать посещение, затем добавлять все смежные вершины этой вер- шины в хвост очереди;

3)  повторять шаг 2, пока не будут посещены все вершины.

> Чтобы избежать повторного обхода вершин, необходимо использовать хеш- множество visited для записи посещенных узлов.
>
> \# === File: graph_bfs.py ===
>
> def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -\> list\[Vertex\]: \"\"\" Обход в ширину.\"\"\"
>
> \# Использование списка смежности для представления графа, чтобы получить
>
> все смежные вершины текущей вершины.
>
> \# Последовательность обхода вершин. res = \[\]
>
> \# Хеш-множество для записи уже посещенных вершин. visited = set\[Vertex\](\[start_vet\])
>
> \# Очередь для реализации поиска в ширину. que = deque\[Vertex\](\[start_vet\])
>
> \# Начало с вершины vet; цикл до тех пор, пока не будут посещены все вершины. while len(que) \> 0:
>
> vet = que.popleft() \# Вершина извлекается из головы очереди. res.append(vet) \# Запись посещенной вершины.
>
> \# Обход всех смежных вершин этой вершины. for adj_vet in graph.adj_list\[vet\]:
>
> if adj_vet in visited:
>
> continue \# Пропуск уже посещенных вершин. que.append(adj_vet) \# В очередь добавляются только
>
> \# непосещенные вершины. visited.add(adj_vet) \# Отметка, что вершина была посещена.
>
> \# Возврат последовательности обхода вершин. return res
>
> Код относительно абстрактен, рекомендуется обратиться к рис. 9.10 для более глубокого понимания.

![](ru/docs/assets/media/image466.jpeg)

> **Рис. 9.10.** Этапы обхода графа в ширину. Шаг 1
>
> ![](ru/docs/assets/media/image468.jpeg)

![](ru/docs/assets/media/image470.jpeg)

> **Рис. 9.10.** *Продолжение*. Шаги 2--3
>
> ![](ru/docs/assets/media/image472.jpeg)

![](ru/docs/assets/media/image474.jpeg)

> **Рис. 9.10.** *Продолжение*. Шаги 4--5
>
> ![](ru/docs/assets/media/image476.jpeg)

![](ru/docs/assets/media/image478.jpeg)

> **Рис. 9.10.** *Продолжение*. Шаги 6--7
>
> ![](ru/docs/assets/media/image480.jpeg)

![](ru/docs/assets/media/image482.jpeg)

> **Рис. 9.10.** *Продолжение*. Шаги 8--9
>
> ![](ru/docs/assets/media/image484.jpeg)

![](ru/docs/assets/media/image486.jpeg)

##### Анализ сложности

> **Рис. 9.10.** *Окончание*. Шаги 10--11
>
> **Временная сложность**: все вершины будут добавляются в очередь и удаляют- ся из нее ровно один раз, что требует времени *O*(\|*V*\|). В процессе обхода смеж- ных вершин, поскольку граф неориентированный, все ребра будут посещены дважды, что занимает время *O*(2\|*E*\|). В целом требуется время *O*(\|*V*\| + \|*E*\|).
>
> **Пространственная сложность**: список res, хеш-множество visited и количе- ство вершин в очереди que максимум равны \|*V*\|, что требует пространства *O*(\|*V*\|).

### Обход в глубину

> **Обход в глубину (DFS)** -- **это метод обхода, при котором сначала ис- следуются все возможные пути до самого конца**, **а затем происходит возврат**. Начиная с левой верхней вершины, посещается какая-либо смеж- ная вершина текущей вершины, пока не будет достигнут конец пути, после чего происходит возврат и опять продолжается обход до конца. Продолжа- ем процесс и так далее, пока все вершины не будут посещены, как показано на рис. 9.11.

![](ru/docs/assets/media/image488.jpeg)

> **Рис. 9.11.** Обход графа в глубину

##### Реализация алгоритма

> Этот алгоритмический подход «до конца и назад» обычно реализуется с помо- щью рекурсии. Подобно обходу в ширину, в обходе в глубину также необходи- мо использовать хеш-множество visited для записи уже посещенных вершин, чтобы избежать их повторного посещения.
>
> \# === File: graph_dfs.py ===
>
> def dfs(graph: GraphAdjList, visited: set\[Vertex\], res: list\[Vertex\], vet: Ver- tex):
>
> \"\"\" Вспомогательная функция для обхода в глубину.\"\"\" res.append(vet) \# Запись посещенной вершины. visited.add(vet) \# Пометка вершины как посещенной. \# Обход всех смежных вершин текущей вершины.
>
> for adjVet in graph.adj_list\[vet\]: if adjVet in visited:
>
> continue \# Пропуск уже посещенной вершины. \# Рекурсивное посещение смежной вершины. dfs(graph, visited, res, adjVet)
>
> def graph_dfs(graph: GraphAdjList, start_vet: Vertex) -\> list\[Vertex\]: \"\"\" Обход в глубину.\"\"\"
>
> \# Использование списка смежности для представления графа, чтобы получить все смежные вершины текущей вершины.
>
> \# Последовательность обхода вершин. res = \[\]
>
> \# Хеш-множество для записи уже посещенных вершин.
>
> visited = set\[Vertex\]()
>
> dfs(graph, visited, res, start_vet) return res
>
> Алгоритм обхода в глубину показан на рис. 9.12.

- **Прямые пунктирные линии** обозначают нисходящую рекурсию, ука- зывая на начало нового рекурсивного метода для посещения новой вер- шины.

- **Изогнутые пунктирные линии** обозначают восходящую рекурсию, указывая на возврат данного рекурсивного метода к месту его начала.

> Для лучшего понимания рекомендуется на примере рис. 9.12 и кода реали- зации мысленно (или с помощью рисунка) смоделировать весь процесс обхода в глубину, включая моменты начала и возврата каждого рекурсивного метода.

![](ru/docs/assets/media/image490.jpeg)![](ru/docs/assets/media/image492.jpeg)

> **Рис. 9.12.** Этапы обхода графа в глубину. Шаги 1--2
>
> ![](ru/docs/assets/media/image494.jpeg)

![](ru/docs/assets/media/image496.jpeg)![](ru/docs/assets/media/image498.jpeg)

> **Рис. 9.12.** *Продолжение*. Шаги 3--5
>
> ![](ru/docs/assets/media/image500.jpeg)

![](ru/docs/assets/media/image502.jpeg)![](ru/docs/assets/media/image504.jpeg)

> **Рис. 9.12.** *Продолжение*. Шаги 6--8
>
> ![](ru/docs/assets/media/image506.jpeg)

![](ru/docs/assets/media/image508.jpeg)![](ru/docs/assets/media/image510.jpeg)

> **Рис. 9.12.** *Окончание*. Шаги 9--11

##### Анализ сложности

> **Временная сложность**: все вершины будут посещены один раз, что требует времени *O*(\|*V*\|). Все ребра будут посещены дважды, что требует времени *O*(2\|*E*\|). В целом требуется время *O*(\|*V*\| + \|*E*\|).
>
> **Пространственная сложность**: список res и хеш-множество visited имеют максимум \|*V*\| вершин, максимальная глубина рекурсии равна \|*V*\|, следователь- но, требуется пространство *O*(\|*V*\|).

#### резюме

##### Ключевые моменты

- Граф состоит из вершин и ребер, его можно задать как множество вер- шин и множество ребер.

- По сравнению с линейными отношениями (список) и отношениями раз- деления (дерево), сетевые отношения (граф) обладают большей степе- нью свободы и, следовательно, более сложны.

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

- Матрица смежности использует матрицу для представления графа, каж- дая строка (столбец) представляет вершину, элементы матрицы пред- ставляют ребра. Значение 1 соответствует наличию ребра между двумя вершинами, значение 0 -- отсутствию. Матрица смежности эффектив- на в операциях добавления, удаления, поиска и изменения, но требует больше пространства.

- Список смежности использует несколько списков для представления графа, *i*-й список соответствует вершине *i* и хранит все смежные верши- ны этой вершины. Список смежности экономнее по сравнению с матри- цей смежности, но из-за необходимости обхода списка для поиска ребра его временная эффективность ниже.

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

> 9.4. Резюме ❖ **263**

- С точки зрения алгоритмических подходов матрица смежности реализу- ет принцип обмена пространства на время, а список смежности -- обмена времени на пространство.

- Графы используются для моделирования различных реальных систем, таких как социальные сети, линии метро и т. д.

- Дерево является частным случаем графа, а обход дерева -- частным слу- чаем обхода графа.

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

- Обход графа в глубину (DFS) -- это метод поиска, который сначала прохо- дит до конца, а затем отступает назад, когда дальнейшего пути нет, часто реализуется на основе рекурсии.

##### Вопросы и ответы

> **Вопрос**. Путь -- это последовательность вершин или ребер?
>
> **Ответ**. В разных языковых версиях «Википедии» определения различа- ются: в английской версии путь -- это последовательность ребер, а в русской версии путь -- это последовательность вершин. Приведем оригинальный текст английской версии: In graph theory, a path in a graph is a finite or infinite se- quence of edges which joins a sequence of vertices.
>
> В этой книге путь рассматривается как последовательность ребер, а не вер- шин. Это связано с тем, что между двумя вершинами может существовать не- сколько соединяющих ребер, и каждое из них соответствует отдельному пути. **Вопрос**. Могут ли существовать в несвязном графе недостижимые вершины?
>
> **Ответ**. В несвязном графе существует по крайней мере две вершины -- та- кие, что одна не достижима из другой. Для обхода несвязного графа необхо- димо установить несколько начальных точек, чтобы обойти все связные ком- поненты графа.
>
> **Вопрос**. Существует ли в списке смежности требование к выбору порядка всех вершин, связанных с данной вершиной?
>
> **Ответ**. Порядок может быть произвольным. Однако на практике может по- требоваться сортировка по определенным правилам, например в порядке до- бавления вершин или в порядке значений вершин, что помогает быстро на- ходить вершины с определенным экстремумом.
>
> Глава 10