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

Материал из Алговики
Перейти к навигации Перейти к поиску
Get Perf.Data

Содержание

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

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

Алгоритм Борувки[1][2] предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе. Алгоритм хорошо параллелизуется и является основой для распределённого алгоритма 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.3 Вычислительное ядро алгоритма

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

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.7 Информационный граф

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

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

1.9 Входные и выходные данные алгоритма

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

3 Литература

  1. Borůvka, Otakar. “O Jistém Problému Minimálním.” Práce Moravské Přírodovědecké Společnosti III, no. 3 (1926): 37–58.
  2. Jarník, Vojtěch. “O Jistém Problému Minimálním (Z Dopisu Panu O. Borůvkovi).” Práce Moravské Přírodovědecké Společnosti 6, no. 4 (1930): 57–63.