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

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

Описание алгоритма

Пока [math]T[/math] не является деревом

1. Для каждой компоненты связанности находим минимальное по весу ребро, которое связывает вершину из данной компоненты с вершиной, не принадлежащей данной компоненте.
2. Добавим в [math]T[/math] все ребра, которые хотя бы для одной компоненты оказались минимальными.

Получившееся множество [math]T[/math] является минимальным остовным деревом графа [math]G[/math].

Реализация

Graph Boruvka(Graph G) while T.size < n init() // у вершины есть поле comp(компонента которой принадлежит вершина) findComp(T) // разбивает граф T на компоненты связынности обычным dfs-ом for uv [math]\in[/math] E if u.comp != v.comp if minEdge[u.comp].w < uv.w minEdge[u.comp] = uv if minEdge[v.comp].w < uv.w minEdge[v.comp] = uv) for k [math]\in[/math] K // K - множество компонент связанности в T T.addEdge(minEdge[k]) return T;

Вход: граф [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] одному множеству. Если нет, то объединяем множества, в которых лежат [math]u[/math] и [math]v[/math], и добавляем ребро [math]uv[/math] к [math]F[/math].

Асимптотика

Время работы внутри главного цикла будет равно [math]O(E + V)[/math](обычный dfs) + [math]O(E)[/math] + [math]O(V)[/math](колличество компонент связанности) = [math]O(E)[/math] Количество итераций которое выполняется главным циклом = [math]O(log(V))[/math] т.к на каждой итерации количество компонент связанности уменьшается в 2 раза.

Литература

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

См. также

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