Графовые алгоритмы

1.

Графовые алгоритмы

2.

Графовые алгоритмы
Обход графа в ширину
Обход графа в глубину
Остовное дерево
Компоненты связности
Топологическая сортировка
Нахождение мостов и точек сочленения
Нахождение циклов в графе
Кратчайшие пути
Потоки в сети
Паросочетания в двудольном графе

3.

Визуализация алгоритмов

4.

Поиск в глубину –
Depth-First Search (DFS)

5.

Поиск в глубину
for x ∈ V do new (x) ← true // инициализация
for x ∈ V do if new (x) then DFS (x)
procedure DFS (v)
visit (v)
// посещение вершины v
new (v) ← false\
for w ∈ Adj (v) do if new (w) then DFS (w)
return

6.

Время поиска в глубину в произвольном графе равно O (|V | + | E |)

7.

Поиск в ширину
Breadth-First Search, BFS

8.

Поиск в ширину

9.

Поиск в ширину
a, b, e, f, c, d, g
Вычислительная сложность алгоритма равна O (|V | + | E |)

10.

Сравнение

11.

Остовные деревья

12.

13.

Поиск в глубину (одна компонента связности)

14.

Поиск в глубину (две компоненты связности)

15.

Компоненты связности
Для поиска компонент связности совершим серию обходов
в глубину.
Запустим dfs из первой вершины. Все вершины, которые он
обошел, отнесем к первой компоненте связности.
Далее ищем непосещенную вершину и запускаем из нее
dfs.
Все посещенные из нее вершины образуют вторую
компоненту связности.
Продолжаем процесс вызовов поиска в глубину пока есть
непосещенные вершины.

16.

Использование поиска в ширину
Поиск кратчайшего пути в невзвешенном графе.
Нахождения решения какой-либо задачи (игры) с наименьшим числом
ходов, если каждое состояние системы можно представить вершиной
графа, а переходы из одного состояния в другое — рёбрами графа.
Классический пример — игра, где робот двигается по полю, при этом
он может передвигать ящики, находящиеся на этом же поле, и
требуется за наименьшее число ходов передвинуть ящики в
требуемые позиции. Решается это обходом в ширину по графу, где
состоянием (вершиной) является набор координат: координаты
робота, и координаты всех коробок.

17.

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

18.

Алгоритм Флойда-Уоршалла
Алгоритм Флойда-Уоршелла – алгоритм для
нахождения кратчайших расстояний между всеми
вершинами взвешенного ориентированного графа
без циклов отрицательного веса с использованием
метода динамического программирования.
Этот алгоритм был одновременно опубликован в
1962 г в статьях Роберта Флойда и
Стивена Уоршелла
Ф

19.

Алгоритм Флойда-Уоршалла
Общая идея
Строится специальная матрица