Алгоритмы и структуры данных (основной поток) 1.

Алгоритмы и структуры данных (2020)

1. Содержание:

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

2. Содержание:

Сильная связность Алгоритм Косарайю Корректность алгоритма Косарайю Мосты в графе, реберная двусвязность

3. Содержание:

Точки сочленения, вершинная двусвязность Алгоритм Тарьяна Корректность алгоритма Тарьяна Обход в ширину Эйлеров граф, критерий

4. Содержание:

Планарность графов Формула Эйлера Теорема Понтрягина-Куратовского Теорема Вигнера Алгоритм Хопкрофта-Тарьяна Гамма-алгоритм, контактная вершина Корректность гамма-алгоритма Асимптотика

5. Содержание:

- Кратчайшие пути в графах

- Задача найти кратчайшие расстояния от одной вершины до остальных.

- Задача найти все пары кратчайших расстояний.

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

- Методы избавления от куба памяти

- Пример использования Алгоритма Флойда

- Алгоритм Флойда при наличии в графе отрицательных циклов

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

6. Содержание:

- асимптотика Форда-Беллмана

- восстановление пути в алгоритме Форда-Беллмана

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

- вариант за квадрат

- Дейкстра с кучей за O(m log n)

- Дейкстра на Фибоначчиевой куче

- Восстановление пути

- дерево доминаторов

7. Содержание:

- замена функции расстояния

- алгоритм Джонсона

- двусторонний алгоритм Дейкстры

- алгоритм A*

- корректность и асимптотика A*

Комментарии: