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

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

Алгоритм Краскала — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Открыт Джозефом Крускалом в 1956 году.

Реализация

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

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

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

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

См. также

• Алгоритм Прима

Литература

• Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. 1956. Vol 7, No. 1. C. 48–50

Ссылки

• Построение минимального остовного дерева