Лекция 5+6. Графы

1.

Графы

2.

Ориентированный, неориентированный граф

3.

Обход в глубину
Лемма о белых путях:
Рассмотрим граф и вершину u в два момента времени -- когда мы покрасили
вершину в серый, и когда покрасили в чёрный. Вершины, которые были
чёрными или серыми, останутся таковыми. Вершины, которые были белыми,
станут чёрными, если (и только если) в них есть путь из u
Поиск цикла

4.

Топологическая сортировка

5.

Связность в графе
Компоненты сильной и слабой связности

6.

Нахождение компонент сильной связности
Алгоритм Косарайю

7.

Компоненты рёберной двусвязности
Мосты

8.

Компоненты вершинной двусвязности
Точки сочленения

9.

Алгоритм Тарьяна для поиска компонент сильной
связности

10.

Обход в ширину. Волновой алгоритм

11.

Критерий существования Эйлерова пути и цикла
в ориентированном и не ориентированном графе
Поиск эйлерова пути и цикла

12.

Гамма-алгоритм

13.

Поиск кратчайших путей

14.

Алгоритм Дейкстры

15.

Фибоначчиева куча

16.

Алгоритм Флойда

17.

Алгоритм Форда-Беллмана

18.

Алгоритм Форда-Беллмана