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

Алгори́тм Бору́вки (или алгоритм Борувки — Соллина) — это алгоритм нахождения минимального остовного дерева в графе.

Впервые был опубликован в 1926 году Отакаром Борувкой^[англ.] в качестве метода нахождения оптимальной электрической сети в Моравии. Несколько раз был переоткрыт, например Флореком, Перкалом и Соллином. Последний, кроме того, был единственным западным учёным из этого списка, и поэтому алгоритм часто называют алгоритмом Соллина, особенно в литературе по параллельным вычислениям.

Алгоритм

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

Алгоритм можно описать так:

1. Изначально, пусть ${\displaystyle T}$ — пустое множество рёбер (представляющее собой остовный лес, в который каждая вершина входит в качестве отдельного дерева).
2. Пока ${\displaystyle T}$ не является деревом (что эквивалентно условию: пока число рёбер в ${\displaystyle T}$ меньше, чем ${\displaystyle V-1}$, где ${\displaystyle V}$ — число вершин в графе):
   • Для каждой компоненты связности (то есть, дерева в остовном лесе) в подграфе с рёбрами ${\displaystyle T}$, найдём самое дешёвое ребро, связывающее эту компоненту с некоторой другой компонентой связности. (Предполагается, что веса рёбер различны, или как-то дополнительно упорядочены так, чтобы всегда можно было найти единственное ребро с минимальным весом).
   • Добавим все найденные рёбра в множество ${\displaystyle T}$.
3. Полученное множество рёбер ${\displaystyle T}$ является минимальным остовным деревом входного графа.

Сложность алгоритма

На каждой итерации число деревьев в остовном лесу уменьшается по крайней мере в два раза, поэтому всего алгоритм совершает не более ${\displaystyle O(\log V)}$ итераций. Каждая итерация может быть реализована со сложностью ${\displaystyle O(E)}$, поэтому общее время работы алгоритма составляет ${\displaystyle O(E\log V)}$ времени (здесь ${\displaystyle V}$ и ${\displaystyle E}$ — число вершин и рёбер в графе, соответственно).

Однако для некоторых видов графов, в частности, планарных, оно может быть уменьшено до ${\displaystyle O(E)}$.[1] Существует также рандомизированный алгоритм построения минимального остовного дерева, основанный на алгоритме Борувки, работающий в среднем за линейное время.

См. также

• Минимальное остовное дерево
• Остовное дерево
• Алгоритм Дейкстры
• Алгоритм Краскала
• Алгоритм обратного удаления
• Алгоритм Прима

Литература

• Седжвик Р. Фундаментальные алгоритмы на C++, часть 5. Алгоритмы на графах. ISBN 5-93772-082-2.

Примечания

1. Eppstein, David (1999), "Spanning trees and spanners", in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425—461; Mareš, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes" (PDF), Archivum mathematicum, 40 (3): 315—320, Архивировано (PDF) 9 мая 2009, Дата обращения: 14 марта 2009 Источник  (неопр.). Дата обращения: 14 марта 2009. Архивировано 9 мая 2009 года..