Алгоритм Краскала
Материал из Википедии — свободной энциклопедии
Алгоритм Краскала находит остовный лес минимального веса в данном графе.
[править] Реализация
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным лесом минимального веса.
До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E × log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку α(E, V) = o(log(E)), общее время работы Алгоритма Краскала составляет O(E × log(E)).
[править] Доказательство корректности алгоритма
Алгоритм Краскала действительно находит остовный лес минимального веса, поскольку он является частным случаем алгоритма Радо — Эдмондса для графического матроида, где независимые множества — ациклические множества рёбер.
