Алгоритмы и структуры данных, часть 2
Санкт-Петербург, весна 2019
Описание
Продолжение изучения базовых алгоритмов, продолжение курса Алгоритмы и структуры данных 1
.
Преподаватели
Список лекций
Способы хранения графов: матрица смежности, списки смежности, матрица инцидентности. Поиск в глубину. Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности. Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин. Выделение компонент сильной связности в орграфах.
Кратчайшие пути в графах. Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину. Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры, оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-ичной кучей).
Нахождение кратчайших путей из одной вершины в графах, в которых есть рёбра отрицательного веса, алгоритм Беллмана-Форда, проверка наличия цикла отрицательного веса. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршалла.
Задача о максимальном потоке. Теорема о минимальном разрезе и максимальном потоке. Алгоритм Форда-Фалкерсона. Алгоритм Эдмондса-Карпа. Задача о паросочетании в двудольном графе.