Андрей Гейн: Остовные деревья — это важная часть теории графов (о которой, вероятно, все программисты когда-нибудь слышали). На лекции разберёмся, что такое остовное дерево и как его находить. Субъективная сложность лекции — две теты из пяти. Содержание: 1:06 Остовное дерево 7:10 Алгоритм Прима 18:54 Вычислительная сложность алгоритма Прима 22:27 Уменьшение сложности алгоритма Прима 25:53 Уменьшение сложности алгоритма Прима для разреженных графов 31:42 Лирическое отступление про возраст алгоритмов 33:21 Алгоритм Краскала 47:23 Система непересекающихся множеств 55:41 Эвристика сжатия путей 1:00:30 Ранговая эвристика 1:07:03 Алгоритм Тарьяна и обратная функция Кермана 1:22:34 Параллелизация алгоритма Краскала 1:25:40 Вопросы
