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

Алгоритм Краскала - алгоритм поиска минимального остовного дерева (остова) во взвешенном ориентированном связном графе.

Идея

Обозначим за [math]T[/math] минимальный остов графа [math]G[/math]. Будем последовательно строить подграф [math]F[/math] графа [math]G[/math] ("растущий лес"), поддерживая инвариант [math]F \subset T[/math]. Начнем с того, что включим в [math]F[/math] все вершины графа [math]G[/math]. Теперь будем обходить множество [math]EG[/math] в порядке увеличения веса ребер. Добавление очередного ребра [math]e[/math] в [math]F[/math] может привести к возникновению цикла в одной из компонент связности [math]F[/math]. В этом случае, очевидно, [math]e[/math] не может быть включено в [math]F[/math]. В противном случае [math]e[/math] соединяет разные компоненты связности [math]F[/math] и из леммы о безопасном ребре следует, что [math]F+e \subset T[/math], и можно добавить это ребро в [math]F[/math].
После обхода всех ребер в [math]F[/math] включены те и только те ребра, которые продолжают его до [math]T[/math], значит, [math]F=T[/math].

Реализация

Вход: граф [math]G = (V, E)[/math]
Выход: минимальный остов [math]F[/math] графа [math]G[/math]
1) [math]F := (V, \varnothing)[/math]
1) Отсортируем [math]E[/math] по весу ребер.
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством [math]V[/math].
3) Перебирая ребра [math]uv \in EG[/math] в порядке увеличения веса, смотрим, одинакового ли представителя для [math]u[/math] и [math]v[/math] возвращает DSU. Если нет, то делаем слияние этих представителей в DSU и полагаем [math]F := F + uv[/math].

Асимптотика

Сортировка [math]E[/math] займет [math]O(ElogE)[/math].
Работа с DSU займет [math]O(E\alpha(E, V))[/math], где [math]\alpha(E, V)[/math] - обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу.
Алгоритм работает за [math]O(E(logE+\alpha(E, V))) = O(ElogE) = O(ElogV^2) = O(ElogV)[/math].

См. также

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