Алгоритм Борувки
Алгори́тм Бору́вки (или алгоритм Борувки — Соллина) — это алгоритм нахождения минимального остовного дерева в графе.
Впервые был опубликован в 1926 году Отакаром Борувкой[англ.] в качестве метода нахождения оптимальной электрической сети в Моравии. Несколько раз был переоткрыт, например Флореком, Перкалом и Соллином. Последний, кроме того, был единственным западным учёным из этого списка, и поэтому алгоритм часто называют алгоритмом Соллина, особенно в литературе по параллельным вычислениям.
Алгоритм
Работа алгоритма состоит из нескольких итераций, каждая из которых состоит в последовательном добавлении рёбер к остовному лесу графа, до тех пор, пока лес не превратится в дерево, то есть, лес, состоящий из одной компоненты связности.
Алгоритм можно описать так:
- Изначально, пусть [math]\displaystyle{ T }[/math] — пустое множество рёбер (представляющее собой остовный лес, в который каждая вершина входит в качестве отдельного дерева).
- Пока [math]\displaystyle{ T }[/math] не является деревом (что эквивалентно условию: пока число рёбер в [math]\displaystyle{ T }[/math] меньше, чем [math]\displaystyle{ V - 1 }[/math], где [math]\displaystyle{ V }[/math] — число вершин в графе):
- Для каждой компоненты связности (то есть, дерева в остовном лесе) в подграфе с рёбрами [math]\displaystyle{ T }[/math], найдём самое дешёвое ребро, связывающее эту компоненту с некоторой другой компонентой связности. (Предполагается, что веса рёбер различны, или как-то дополнительно упорядочены так, чтобы всегда можно было найти единственное ребро с минимальным весом).
- Добавим все найденные рёбра в множество [math]\displaystyle{ T }[/math].
- Полученное множество рёбер [math]\displaystyle{ T }[/math] является минимальным остовным деревом входного графа.
Сложность алгоритма
На каждой итерации число деревьев в остовном лесу уменьшается по крайней мере в два раза, поэтому всего алгоритм совершает не более [math]\displaystyle{ O(\log V) }[/math] итераций. Каждая итерация может быть реализована со сложностью [math]\displaystyle{ O(E) }[/math], поэтому общее время работы алгоритма составляет [math]\displaystyle{ O(E \log V) }[/math] времени (здесь [math]\displaystyle{ V }[/math] и [math]\displaystyle{ E }[/math] — число вершин и рёбер в графе, соответственно).
Однако для некоторых видов графов, в частности, планарных, оно может быть уменьшено до [math]\displaystyle{ O(E) }[/math].[1] Существует также рандомизированный алгоритм построения минимального остовного дерева, основанный на алгоритме Борувки, работающий в среднем за линейное время.
См. также
- Минимальное остовное дерево
- Остовное дерево
- Алгоритм Дейкстры
- Алгоритм Краскала
- Алгоритм обратного удаления
- Алгоритм Прима
Литература
- Седжвик Р. Фундаментальные алгоритмы на C++, часть 5. Алгоритмы на графах. ISBN 5-93772-082-2.
Примечания
- ↑ Eppstein, David (1999), Spanning trees and spanners, in Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry, Elsevier, с. 425–461; Mareš, Martin (2004), Two linear time algorithms for MST on minor closed graph classes, Archivum mathematicum Т. 40 (3): 315–320, <http://www.emis.de/journals/AM/04-3/am1139.pdf> Архивная копия от 9 мая 2009 на Wayback Machine.
