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


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

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

Алгоритм

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

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

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

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

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



    Имя:*
    E-Mail:
    Комментарий:
    Информационный некоммерческий ресурс fccland.ru ©
    При цитировании информации ссылка на сайт обязательна.
    Копирование материалов сайта ЗАПРЕЩЕНО!