Алгоритм Краскала

Алгоритм Краскала строит минимальное остовное дерево взвешенного графа жадно: сортируем все рёбра по весу и идём от лёгких к тяжёлым, добавляя ребро только тогда, когда оно не создаёт цикл с уже взятыми. После $n-1$ добавлений остов готов. Жадность здесь не эвристика, а стратегия с гарантией: лёгкое ребро поперёк разреза всегда можно обменять на любое более тяжёлое ребро финального дерева, не увеличивая суммарный вес — поэтому оптимальность доказывается индукцией по шагам. Теория остовов — в уроке деревья и алгоритмы.

Проверку цикла выполняют системы непересекающихся множеств (DSU) со сжатием путей, и тогда сложность $O(m\log m)$ упирается в сортировку рёбер. Родственник — алгоритм Прима: тот растит одно дерево от стартовой вершины, каждый раз вытягивая ближайшее ребро; Краскал же держит лес, который постепенно срастается. Результат по весу одинаков, но характер разный: на плотных графах быстрее Прим, на разреженных или уже отсортированных данных Краскал почти бесплатен. Сводка графовых алгоритмов с псевдокодом — в шпаргалке по графам и алгоритмам, определения — в термине граф.