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

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

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

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

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

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

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

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

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

1.4 Макроструктура алгоритма

В задаче требуется указать в данном связном взвешенном графе дерево, соединяющее все его вершины и имеющее наименьший возможный суммарный вес рёбер.

Классический пример (из статьи Борувки) – спроектировать наиболее дешёвую электрическую сеть, зная стоимость устройства каждого участка электрической линии.

Пусть задан связный граф [math]G=(V,E)[/math] с вершинами [math]V=(v_1,v_2,…,v_n)[/math] и рёбрами [math]E=(e_1,e_2,…,e_m)[/math]. Каждому ребру [math]e∈E[/math] приписан вес [math]w(e)[/math].

Требуется построить дерево [math]T^*⊆E[/math], связывающее все вершины, и имеющее наименьший возможный вес среди всех таких деревьев:

[math]w(T^* )=min┬T⁡〖w(T)〗[/math]

где вес множества рёбер есть сумма их весов:

[math]w(T)=∑_(e∈T)▒〖w(T)〗[/math]

Если граф [math]G[/math] не является связным, то дерева, связывающего все вершины, не существует.

В этом случае необходимо найти минимальной остовное дерево для каждой компоненты связности [math]G[/math]. Набор таких деревьев называется минимальным остовным лесом (сокращённо MSF – Minimum Spanning Forest).

1.5 Схема реализации последовательного алгоритма

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

1. В самом начале каждая вершина является отдельным фрагментом.

2. На каждом шаге:

• Для каждого фрагмента определяется минимальное по весу исходящее ребро.

• Минимальные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты объединяются.

3. Алгоритм останавливается, когда остаётся только один фрагмент, либо когда ни у одного из фрагментов нет исходящих рёбер.

Поиск минимальных исходящих рёбер может выполняться независимо для каждого фрагмента. Таким образом, данную стадию вычислений можно эффективно параллелизовать (в том числе с использованием массового параллелизма графических ускорителей).

Объединение фрагментов также может быть реализовано параллельно, с использованием описанной выше параллельной версии структуры Union-Find.

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

1. В начале итерации счётчик активных фрагментов обнуляется.

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

3. На этапе объединения фрагментов счётчик уменьшается на единицу каждый раз, когда операция UNION(u, v) вернула значение истина.

Если в конце итерации счётчик равен 0 или 1, то вычисления останавливаются. Параллелизм возможен на этапе сортировки рёбер по весу, однако основной ход алгоритма является последовательным.

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

Последовательная сложность алгоритма Борувки для графа с [math]n[/math] вершинами и [math]m[/math] рёбрами составляет [math]O(m*ln(n))[/math] операций.

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

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

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

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

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