Алгоритмы (базовый поток) 5. Простейшие графы, 0-k, 0-1 BFS

Дата лекции: 16.03.23
Лектор: Ибрагимов Б. Л.

00:00:00 Начало
00:00:05 Основы теории графов
00:07:06 Способы представления графов в памяти
00:08:10 Список ребер
00:10:54 Сортированный список ребер
00:13:10 Матрица смежности
00:17:33 Списки смежности
00:26:08 Замечание про неориентированные графы
00:31:11 Обход графа в ширину (BFS)
00:38:58 Поиск кратчайших путей с помощью BFS
00:47:06 Время работы алгоритма поиска кратчайших путей
00:52:15 Корректность алгоритма
01:05:24 BFS для взвешенных графов (0-1 граф)
01:09:11 BFS для взвешенных графов (0-k граф, неэффективный метод)
01:11:03 BFS для взвешенных графов (0-k граф, спойлер эффективного метода)

Съёмка: Казанцева Таня
Монтаж: Степашин Егор