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

Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера.

Алгоритм описан Джозефом Краскалом в 1956 году, этот алгоритм почти не отличается от алгоритма Борувки, предложенного Отакаром Борувкой в 1926 году.

Формулировка

В начале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса. Подробное описание алгоритма можно найти в литературе.

Оценка

До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E × log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять её за константу, таким образом, общее время работы алгоритма Краскала можно принять за O(E * log(E)).

Доказательство корректности алгоритма

Алгоритм Краскала действительно находит остовное дерево минимального веса, поскольку он является частным случаем алгоритма Радо — Эдмондса для графического матроида, где независимые множества — ациклические множества рёбер.

Пример