Алгоритм Краскала: минимальное остовное дерево

Алгоритм Краскала находит минимальное остовное дерево взвешенного неориентированного графа: соединяет все вершины рёбрами с минимальной суммой весов. Его правило короткое: рассматривать рёбра по возрастанию веса и брать очередное, только если оно не замыкает цикл. До конца работы получается не одно растущее дерево, а лес из нескольких компонент, которые постепенно объединяются. В калькуляторе измените вес ребра В–Д и посмотрите, как меняется порядок проверок и итоговая сумма.
Что требуется построить
Пусть вершины обозначают объекты, а ребро между двумя вершинами - допустимое соединение с заданной стоимостью. Остовное дерево содержит все вершины исходного связного графа, остаётся связным и не имеет циклов. Если вершин , в любом таком дереве ровно ребро. Удаление любого из них нарушит связность, а добавление ещё одного создаст цикл.
Минимальное остовное дерево, или МОД, имеет наименьшую сумму весов среди всех остовных деревьев данного графа. Оно минимизирует стоимость всей сети, а не расстояние от выбранной вершины до остальных. Для задачи кратчайших путей нужны другие критерии и алгоритмы. Веса могут быть нулевыми и отрицательными: правило сортировки от этого не меняется.
Для несвязного графа одного остова всех вершин не существует. Если продолжить процедуру Краскала до конца списка рёбер, получится минимальный остовный лес: отдельное минимальное дерево для каждой связной компоненты, включая изолированные вершины как деревья без рёбер.
Как работает выбор рёбер
В начале каждая вершина образует отдельную компоненту. Отсортируем рёбра по неубыванию веса. Для каждого ребра проверяем его концы: если они в разных компонентах, добавляем ребро и объединяем компоненты; если уже в одной, пропускаем. Во втором случае между концами уже есть путь из выбранных рёбер, поэтому новое ребро замкнуло бы цикл.
Для связного графа можно остановиться, как только выбрано ребро: поскольку циклов нет, полученный лес с таким числом рёбер обязательно связен. При равных весах их можно проверять в любом порядке. Для воспроизводимости удобно заранее договориться о порядке равных рёбер, как в калькуляторе; другой порядок способен дать другое дерево той же минимальной стоимости.
Пример: пять вершин и шесть рёбер
Возьмём граф с вершинами А, Б, В, Г, Д. Его рёбра уже перечислены по возрастанию: А–Б с весом 1, Б–В с весом 2, А–В с весом 3, Б–Г с весом 4, В–Г с весом 5 и В–Д с весом 6. Проследим не только выбор, но и состояние компонент.
| Ребро | Решение | Причина и итог |
|---|---|---|
| А–Б, 1 | Взять | Соединяет отдельные А и Б; вес 1. |
| Б–В, 2 | Взять | Присоединяет В к компоненте АБ; вес 3. |
| А–В, 3 | Пропустить | Путь А–Б–В уже есть: возник бы цикл. |
| Б–Г, 4 | Взять | Присоединяет Г; вес 7. |
| В–Г, 5 | Пропустить | В и Г уже связаны через Б. |
| В–Д, 6 | Взять | Присоединяет последнюю вершину; вес 13. |
Итак, получаем рёбра А–Б, Б–В, Б–Г и В–Д. Их четыре, все пять вершин связаны, а сумма весов равна . Ребро В–Д обязательно для этого конкретного графа: других рёбер у Д нет. Если уменьшить его вес ползунком, оно будет рассмотрено раньше, но всё равно войдёт в остов.

В таблице каждое решение принимается по компонентам на текущем шаге. Например, А–В весом 3 дешевле Б–Г весом 4, но его не берут: низкой цены недостаточно, если концы уже связаны.
Почему жадный выбор работает
Ключ к доказательству - свойство разреза. Разделим вершины на два непустых множества. Ребро, у которого концы лежат по разные стороны, пересекает разрез. Лёгчайшее ребро такого разреза можно включить хотя бы в одно минимальное остовное дерево; при равных весах оно не обязательно входит в каждое из них.
Пусть Краскал рассматривает ребро , соединяющее две разные компоненты выбранного леса. Возьмём разрез между одной из этих компонент и остальными вершинами. Ранее выбранные рёбра его не пересекают. У любого пересекающего разрез ребра с меньшим весом концы и тогда находились бы в разных компонентах: компоненты только объединяются. Значит, алгоритм уже взял бы такое ребро. Следовательно, - одно из самых лёгких на этом разрезе.
Чтобы увидеть, почему выбор безопасен, предположим, что некоторый минимальный остов уже содержит все выбранные рёбра, но не содержит . Добавление создаёт в нём цикл. На этом цикле есть другое ребро, пересекающее тот же разрез; его вес не меньше веса , и среди выбранных рёбер его нет. Заменим его на : связность сохранится, число рёбер останется прежним, а вес не увеличится. Получится минимальный остов, содержащий и прежний выбор, и . Повторяя рассуждение, получаем корректность всего алгоритма.
Как проверить готовый ответ
После трассировки полезно отделить проверку допустимости от проверки минимальности. Сначала перечислите все вершины и убедитесь, что между любыми двумя есть путь по выбранным рёбрам. Затем проверьте отсутствие цикла: для связного графа достаточно удостовериться, что выбрано ровно ребро. В нашем примере из А можно пройти через Б и В до Д, а до Г - через Б; все пять вершин действительно охвачены.
Эти проверки доказывают только то, что перед нами остовное дерево. Сами по себе связность и число рёбер не гарантируют минимальную сумму. Например, замена А–Б весом 1 на А–В весом 3 сохраняет связность и четыре ребра, но увеличивает вес с 13 до 15. Обоснование оптимальности требует свойства разреза либо корректной трассировки Краскала с проверкой каждого более дешёвого ребра.
При ручном решении удобно вести рядом две записи: список компонент и сумму принятых весов. После принятия ребра объединяйте именно две компоненты, содержащие его концы; после пропуска не меняйте ни компоненты, ни сумму. Такая таблица помогает найти ошибку в конкретном шаге, даже когда итоговое число случайно совпало с правильным.
Как проверять циклы с помощью DSU
На бумаге достаточно выписывать компоненты фигурными скобками. В программе удобна система непересекающихся множеств, DSU или Union-Find. Она поддерживает две операции: возвращает представителя компоненты вершины , а объединяет компоненты. Если представители концов совпадают, ребро пропускают; иначе принимают и вызывают объединение.
отсортировать рёбра по неубыванию веса
создать отдельное множество для каждой вершины
для каждого ребра (u, v, вес):
если find(u) ≠ find(v):
добавить ребро в ответ
union(u, v)
если выбрано n − 1 рёбер: остановиться
Для несвязного графа условие остановки по рёбрам не выполнится: после исчерпания списка нужно сообщить, что получен лес. Важная деталь ввода - хранить список всех вершин отдельно от рёбер, иначе изолированную вершину легко потерять. Сжатие путей и объединение по рангу или размеру ускоряют операции DSU. О применениях и устройстве таких структур подробнее рассказано в статье про алгоритм Тарьяна.
Сложность и сравнение с Примом
Для рёбер и вершин сортировка сравнениями занимает , инициализация DSU - , а все проверки и объединения с указанными оптимизациями - амортизированно. Здесь - очень медленно растущая обратная функция Аккермана. Полная оценка с учётом изолированных вершин: ; обычно основная работа приходится на сортировку. Память для списка рёбер и DSU составляет .
Алгоритм Прима решает ту же задачу, но начинает с одной вершины и расширяет одну связную компоненту. Краскал же выбирает рёбра глобально и может долго поддерживать несколько деревьев. Оба подхода дают минимальный вес, хотя при равных весах могут построить разные остовы. Краскал особенно естественен, когда граф задан списком рёбер; выбор реализации зависит от представления графа и ограничений задачи.
Слово «дерево» встречается и в других структурах, но цель там иная: например, AVL-дерево поддерживает эффективный поиск с помощью балансировки, а B-дерево организует ключи для работы с блоками данных. В остовной задаче, напротив, выбирают рёбра уже заданного графа по суммарному весу.
Частые ошибки
- Брать каждое следующее дешёвое ребро. Перед добавлением всегда проверяйте, не связаны ли его концы уже выбранными рёбрами.
- Проверять цикл в исходном графе. Проверка относится только к текущему выбранному лесу: циклы в исходном графе допустимы.
- Останавливать работу после первого объединения всех встреченных вершин. Учитывайте полный список вершин, включая изолированные, и проверяйте число компонент.
- Считать ответ единственным при равных весах. Разные наборы рёбер могут иметь одинаковый минимальный вес.
- Путать вес дерева с кратчайшим маршрутом. МОД минимизирует сумму всех своих рёбер, а не длину пути между каждой парой вершин.
FAQ
Можно ли применять Краскала при отрицательных весах?
Да. Отсортируйте веса в обычном порядке, начиная с самых отрицательных, и используйте ту же проверку цикла. Доказательство через разрез не требует положительных весов.
Что будет, если граф несвязен?
Алгоритм построит минимальный остовный лес по компонентам. Дерево, соединяющее все вершины, при отсутствии связывающих рёбер построить невозможно.
Обязательно ли минимальное дерево единственно?
Нет. Различные веса рёбер гарантируют единственность МОД, но равные веса сами по себе ещё не доказывают наличие нескольких решений. Нужно проверить, можно ли заменить рёбра без увеличения суммы.
Коротко
Краскал сортирует рёбра по весу, последовательно объединяет разные компоненты и пропускает рёбра, создающие цикл. В связном графе после принятых рёбер получается минимальное остовное дерево; свойство разреза объясняет, почему каждый такой выбор безопасен.
Читайте также

Алгоритм Прима - как построить остовное дерево по шагам
Разбираем, как алгоритм Прима шаг за шагом строит минимальное остовное дерево графа: идея жадного выбора, лемма о разрезе и трассировка на конкретном примере.

Алгоритм Хопкрофта-Карпа: паросочетание по фазам
Алгоритм Хопкрофта-Карпа находит максимальное паросочетание в двудольном графе. Разбираем поиск кратчайших цепей, BFS и DFS, пример двух фаз и оценку сложности.

Обход графа в ширину: очередь, слои и кратчайший путь
Обход графа в ширину: как очередь раскладывает вершины по слоям, почему номер слоя равен кратчайшему расстоянию в невзвешенном графе, как восстановить путь по предкам и проверить двудольность.

Хроматический полином графа: как считать и применять
Что такое хроматический полином графа, как его вычислить через теорему об удалении и стягивании ребра, свойства коэффициентов и связь с хроматическим числом. Формулы и пошаговый пример.

Максимальное независимое множество в графе: разбор
Независимое множество вершин графа: чем различаются максимальное и наибольшее множество, как связаны число независимости и вершинное покрытие, как искать ответ алгоритмами.

Задача о k-центрах в графе: постановка и алгоритмы
Что такое задача о k-центрах в графе: постановка как минимаксная задача размещения, NP-трудность, жадный 2-приближённый алгоритм Гонзалеса и связь с радиусом графа.