Алгоритмы и структуры данных 10. Минимальное остовное дерево. Прим, Крускал и Борувка. СНМ

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики Лекция прочитана 7 апреля 2022 года Лектор: Степанов Илья Даниилович Оператор: Жулябина Ирина Монтаж: Жильцов Игорь 0:00 - Завершение Форда-Беллмана 8:02 - Минимальные остовы. Определения 10:30 - Пример 13:00 - Лемма о безопасном ребре 21:45 - Алгоритм Прима 24:10 - Реализация пересчёта. O(N^2) 27:28 - Оптимизация бинкучей до O(M log N) или фибоначчиевой кучей до O(M + N log N) 29:16 - Алгоритм Крускала 31:23 - Вспомогательная структура данных: система непересекающихся множеств (СНМ/DSU) 42:25 - Асимптотика эвристики эвристики объединения по рангу 45:20 - Эвристика сжатия путей 49:17 - Асимптотика эвристики сжатия путей (б/д). Функция Аккермана 54:50 - Возвращаемся к Крускалу. Алгоритм + время работы 57:39 - Алгоритм Борувки 1:00:30 - Контрпример к алгоритму, выбирающему произвольное ребро 1:03:05 - Корректность алгоритма Борувки. Построенный граф - дерево 1:14:15 - Построенное дерево имеет минимальный возможный вес (является минимальным остовом) 1:18:48 - Асимптотика 1:21:07 - Зачем нужен алгоритм Борувки? Анонс задачи на семинар