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

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

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

Алгоритм

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

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

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

Сложность алгоритма

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

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

См. также

Литература

Примечания

  1. (1999), "Spanning trees and spanners", in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry , Elsevier, pp. 425—461 ; Mareš, Martin (2004), (PDF) , Archivum mathematicum , 40 (3): 315—320 . Дата обращения: 14 марта 2009. Архивировано 9 мая 2009 года. .
Источник —

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