|
Алгоритм БорувкиАлгоритм Борувки, алгоритм нахождения минимального остовного дерева в графе. Впервые был опубликован в 1926 году Отакаром Борувкой в качестве метода нахождения оптимальной электрической сети в Моравии. Несколько раз был переоткрыт, например Флореком,Перкалом и Соллином. Последний, кроме того, был единственным западным ученым из этого списка, и поэтому алгоритм часто называют алгоритмом Соллина, особенно в литературе попараллельным вычислениям. Работа алгоритма состоит из нескольких итераций, каждая из которых состоит в последовательном добавлении рёбер к остовному лесу графа, до тех пор, пока лес не превратится в дерево, то есть, лес, состоящий из одной компоненты связности. В псевдокоде, алгоритм можно описать так:
На каждой итерации число деревьев в остовном лесу уменьшается по крайней мере в два раза, поэтому всего алгоритм совершает не более O(log V) итераций. Каждая итерация может быть реализована со сложностью O(E), поэтому общее время работы алгоритмы составляет O(Elog V) времени (здесь V и E — число вершин и рёбер в графе, соответственно). Однако для некоторых видов графов, в частности, планарных, оно может быть уменьшено до O(E). Существует также рандомизированный алгоритм построения минимального остовного дерева, основанный на алгоритме Борувки, работающий в среднем за линейное время. |
Loading
|