Motivation

Алгоритм Краскала хранит растущий лес выбранных ребер в структуре union-find. Чтобы безопасно добавить ребро, он проверяет, находятся ли две конечные точки уже в одном и том же множестве (это создало бы цикл).

Зачем изучать алгоритм Краскала?

• Реальные MST: проектирование сетей, кластеризация и прокладка кабеля или дорог с минимальными затратами.
• Union-find: красивая, многократно используемая структура для отслеживания связности, которая встречается повсюду в информатике.
• Жадная корректность: еще один пример того, как постоянный выбор самого дешевого безопасного варианта приводит к глобальному оптимуму.

Все минимальные остовные деревья графа используют один и тот же мультимножество весов ребер, поэтому общий вес (и самое тяжелое ребро) уникальны.