> For the complete documentation index, see [llms.txt](https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/26.-dinamicheskie-struktury-dannykh.-grafy.-algoritmy-obkhoda-grafa-v-shirinu-i-glubinu.-primery..md).
# 26. Динамические структуры данных. Графы. Алгоритмы обхода графа в ширину и глубину. Примеры.
## **Динамическая структура данных**
* Это структуры данных, память под которые выделяется и освобождается по мере необходимости. Примером таких структур можно считать деревья, списки, очередь, стек.
## Граф
Это абстрактный тип данных, который предназначен для реализации понятий неориентированного и ориентированного графа из области теории графов в математике.
**Структура данных графа** состоит из конечного набора вершин вместе с набором неупорядоченных пар этих вершин для неориентированного графа или набором упорядоченных пар для ориентированного графа.
## Область применения графов
* Геолокация
* Планирование процессов
* Компьютерные сети
* Структура программы
* Химические соединения
* Связи между людьми
## Основные понятия теории графов
**Ориентированный граф** - G(V, E) - пара из V(конечного множества) и Е(подмножества декартового произведения множества V\*V).
**Неориентированный граф** - ребра есть неупорядоченные пары. Если для любой пары вершин существует путь, граф неориентированный.
**Взвешенный граф** - граф, в котором каждому ребру приписан вес. С(U, V)
Взвешенный граф
**Вершины графа** - элементы множества V.
**Ребра графа** - элементы множества Е.
**Петля** - ребро из вершины Vi в само себя.
Вершины Vi и Vj **смежны**, если между ними имеется связь (Vi, Vj).
**Путем** из V0 в Vn называется последовательность рёбер таких, что Е1 = (V0, V1), E2 = (V1, V2)... En = (Vn-1, Vn)
**Простым путем** называется путь, в котором все вершины попарно различны.
**Длина пути** - количество рёбер в пути.
**Цикл** - путь, в котором V0=Vn.
**Связанная компонента вершины V** - множество вершин неориентированного графа до которых существует путь из V.
## Обход графа. Поиск в ширину(BFS)
Поиск в ширину от исходной вершины - просмотр всех вершин графа в порядке возрастания расстояния от исходной вершины.
Алгоритм работает следующим образом:
1. Начните с размещения любой вершины графа в конце очереди.
2. Возьмите передний элемент очереди и добавьте его в список посещенных.
3. Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в конец очереди.
4. Продолжайте повторять шаги 2 и 3, пока очередь не опустеет.
### Пример BFS
Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере. Мы используем неориентированный граф с 5 вершинами.
[](https://evileg.com/users/mafulechka/albums/photo/758/)
Мы начнем с вершины 0, алгоритм BFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.
[](https://evileg.com/users/mafulechka/albums/photo/759/)
Затем мы посещаем элемент в начале очереди, то есть 1, и переходим к соседним узлам. Так как 0 уже был посещен, мы посещаем 2.
[](https://evileg.com/users/mafulechka/albums/photo/760/)
У вершины 2 есть соседняя не посещенная вершина 4, поэтому мы добавляем ее в конец очереди и посещаем 3, которая находится в начале очереди.
[](https://evileg.com/users/mafulechka/albums/photo/761/)
[](https://evileg.com/users/mafulechka/albums/photo/762/)
В очереди остается только 4, поскольку единственный соседний узел с 3, то есть 0, уже посещен. Мы посещаем вершину 4.
[](https://evileg.com/users/mafulechka/albums/photo/763/)
Поскольку очередь пуста, мы завершили обход в ширину графика.
### Особенности алгоритма
1. Каждая вершина обрабатывается не более 1 раза
2. Легко найти кратчайший путь
3. Легко найти обратный путь
**Сложность алгоритма:** О(|V|+|E|)
Алгоритм реализован на псевдокоде. Для реализации на Си смотрите[ здесь.](https://evileg.com/ru/post/512/)
```
create a queue Q
mark v as visited and put v into Q
while Q is non-empty
remove the head u of Q
mark and enqueue all (unvisited) neighbours of u
```
## Обход в глубину (Depth-First Search, DFS)
Список смежности - это один из способов представления графа:
список смежности для данного графа
Для каждой вершины (первый столбик) мы составляем список смежных ей вершин, то есть список вершин с которыми у данной есть общие ребра(ребро инцидентное данным вершинам).
### Алгоритм поиска
Начнем мы с вершины “0”. В первую очередь алгоритм поиска в глубину поместит ее саму в список “Пройденные” (на изображении “Visited”), а ее смежные вершины — в стек.
Выберите элемент (вершину) и поместите его в список “Пройденные”.
Затем мы берем следующий элемент сверху стека, т.е. к вершину “1”, и переходим к ее соседним вершинам. Поскольку вершина “0” уже пройдена, следующая вершина “2”.
Обход элемента на вершине стека.
Вершина “2” смежна непройденной вершине “4”, следовательно мы добавляем ее наверх стека и проходим ее.
Вершина “2” смежна непройденной вершине “4”, следовательно мы помещаем ее в верх стека.
Добавляем вершину “4” в список “Пройденные” после прохождения.
После того, как мы пройдем последний элемент (вершину “3”), в стеке не останется непройденных смежных вершин, и таким образом мы завершили обход графа в глубину.
После проверки всех смежных вершин для вершины “3” стек остался пустым, а значит алгоритм обхода графа в глубину завершил свою работу.
:star: Код реализован на С++! Реализован только сам алгоритм, полный код [здесь.](https://habr.com/ru/companies/otus/articles/660725/)
void Graph::DFS(int vertex) {
visited[vertex] = true;
list<int> adjList = adjLists[vertex];
cout << vertex << " ";
list<int>::iterator i;
for (i = adjList.begin(); i != adjList.end(); ++i)
if (!visited[*i])
DFS(*i);
}
