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

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

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

Алгоритм Борувки предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе. Алгоритм хорошо параллелизуется и является основой для распределённого алгоритма 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] является отдельным фрагментом. На очередном шаге у каждого фрагмента выбирается исходящее ребро минимального веса (если такое ребро существует). Выбранные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты склеиваются.

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

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

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