Графы. Поиск в глубину (DFS). Хранение графа в программе

Определение
Граф – это набор вершин, некоторые пары из которых соединены между собой рёбрами.
Связный граф – это граф, из любой вершины которого по рёбрам можно попасть в любую другую.
Направленный граф – это граф, по рёбрам которого можно передвигаться только в одном заданном направлении.
Ациклический граф – это граф, не содержащий циклов.
Дерево – это связный граф, имеющий N вершин и N-1 ребро.
Взвешенный граф – это граф, в котором каждое ребро имеет свой вес (обычно длину).
Компонента связности – максимальный по включению связный подграф.

Задача:
Охарактеризуйте граф:
1
2
3
4
5
6
7
8

Задача:
Охарактеризуйте граф:
1
2
3
4
5
6
7
8
3
2
4
1
5
2
1

Задача:
Охарактеризуйте граф:
1
2
3
4
5
6
8
7

Поиск (обход) в глубину (DFS)
Для каждой вершины графа будем хранить её цвет. Пусть изначально вершины будут белыми, когда мы в них входим, они будут становиться серыми, а когда выходим – чёрными.
Будем перебирать вершины графа. Если встречаем белую вершину – запускаем из неё поиск в глубину.
Во время поиска в глубину перебираем все вершины, смежные той, в которой сейчас находится алгоритм, и по очереди запускаем из них поиск в глубину.
Если поиск запущен не из белой вершины, то дальше его продолжать не следует.

Поиск в глубину. Пример. Шаг 0
7
2
6
5
8
3
4
1
1
3
2
5
4
6
7

Поиск в глубину. Пример. Шаг 1
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 2
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 3
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 4
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 5
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 6
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 7
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 8
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 9
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 10
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 11
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 12
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 13
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 14
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 15
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 16
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 17
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 18
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 19
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 20
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 21
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 22
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 23
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 24
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 25
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 26
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 27
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 28
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 29
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Поиск в глубину. Пример. Шаг 30
7
2
6
5
8
3
4
1
1
3
2
6
7
5
4

Хранение графа в программе
Создадим собственную структуру Node для хранения информации о вершине графа.
В Node будем хранить цвет самой вершины и перечень смежных вершин.
Граф будем хранить в виде массива (вектора) вершин.

Реализация поиска в глубину
Поиск в глубину реализуется в виде рекурсивной функции, критерием остановки которой является повторное посещение вершины.