Алгоритм Борувки

Алгоритм Борувки — алгоритм поиска минимального остовного дерева (minimum spanning tree, MST) во взвешенном неориентированном связном графе.Впервые был опубликован в 1926 году Отакаром Борувкой.

Идея

Будем последовательно строить подграф $F$ графа $G$ ("растущий лес"), поддерживая следующий инвариант: на каждом шаге $F$ можно достроить до некоторого MST. Начнем с того, что включим в $F$ все вершины графа $G$. Теперь будем обходить множество $EG$ в порядке увеличения веса ребер. Добавление очередного ребра $e$ в $F$ может привести к возникновению цикла в одной из компонент связности $F$. В этом случае, очевидно, $e$ не может быть включено в $F$. В противном случае $e$ соединяет разные компоненты связности $F$, тогда существует разрез $\langle S, T \rangle$ такой, что одна из компонент связности составляет одну его часть, а оставшаяся часть графа - вторую. Тогда $e$ и есть минимальное ребро, пересекающее этот разрез. Значит, из леммы о безопасном ребре следует, что $F+e$ можно продолжить до MST, поэтому добавим это ребро в $F$.
Несложно понять, что после выполнения такой процедуры получится остовное дерево, при этом его минимальность вытекает из леммы о безопасном ребре.

Реализация

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

Асимптотика

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

Литература

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

См. также

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