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

Свойства и структура алгоритма

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

Алгоритм Борувки предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе. Алгоритм хорошо параллелизуется и является основой для распределённого алгоритма GHS.

Математическое описание алгоритма

Пусть задан связный неориентированный граф [math]\displaystyle{ G = (V, E) }[/math] с весами рёбер [math]\displaystyle{ f(e) }[/math]. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).

Алгоритм Борувки основан на следующих двух свойствах задачи:

• Минимальное ребро фрагмента. Пусть [math]\displaystyle{ F }[/math] – фрагмент минимального остовного дерева и [math]\displaystyle{ e_F }[/math] – ребро наименьшего веса, исходящее из [math]\displaystyle{ F }[/math] (т.е. ровно один его конец является вершиной из [math]\displaystyle{ F }[/math]). Если ребро [math]\displaystyle{ e_F }[/math] единственно, то оно принадлежит минимальному остовному дереву.
• Схлопывание фрагментов. Пусть [math]\displaystyle{ F }[/math] – фрагмент минимального остовного дерева графа [math]\displaystyle{ G }[/math], а граф [math]\displaystyle{ G' }[/math] получен из [math]\displaystyle{ G }[/math] склеиванием вершин, принадлежащих [math]\displaystyle{ F }[/math]. Тогда объединение [math]\displaystyle{ F }[/math] и минимального остовного дерева графа [math]\displaystyle{ G' }[/math] даёт минимальное остовное дерево исходного графа [math]\displaystyle{ G }[/math].

В начале работы алгоритма каждая вершина графа [math]\displaystyle{ G }[/math] является отдельным фрагментом. На очередном шаге у каждого фрагмента выбирается исходящее ребро минимального веса (если такое ребро существует). Выбранные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты склеиваются.

Последовательная сложность алгоритма

Последовательная сложность всех трёх перечисленных алгоритмов для графа с [math]\displaystyle{ n }[/math] вершинами и [math]\displaystyle{ m }[/math] рёбрами составляет [math]\displaystyle{ O(m ln⁡ n ) }[/math] операций.

Ресурс параллелизма алгоритма

Алгоритму Борувки обладает большим потенциалом параллелизма, так как его основная операция (выбор минимального исходящего ребра во фрагменте) может исполнятся независимо для каждого фрагмента.

Программная реализация алгоритма

Существующие реализации алгоритма

• C++, MPI: Parallel Boost Graph Library; функции dense_boruvka_minimum_spanning_tree, boruvka_then_merge, boruvka_mixed_merge сочетают алгоритм Борувки и алгоритм Крускала.