212
правок
Изменения
Нет описания правки
<b>Алгоритм Борувки</b> (англ. ''Borůvka's algorithm'') {{---}} алгоритм поиска [[Остовные деревья: определения, лемма о безопасном ребре | минимального остовного дерева (англ. ''minimum spanning tree, MST'') ]] во взвешенном неориентированном связном графе.
Впервые был опубликован в 1926 году Отакаром Борувкой.
==Описание алгоритма==
# Изначально все ребра каждая вершина графа <tex>G</tex> не окрашены, а каждая вершина графа {{---}} тривиальное дерево, а ребра не принадлежат никакому дереву.# Для каждого дерева <tex> T </tex> найдем минимальное инцидентное ему ребро. Окрасим Добавим все такие ребра.
# Повторяем шаг <tex> 2 </tex> пока в графе не останется только одно дерево <tex> T </tex>.
Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В <tex>T</tex> могут быть добавлены все три ребра. Избежать эту проблему можно, например, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.
==Доказательство корректности==
==Реализация==
У вершины есть поле <tex>\mathtt{comp }</tex> {{---}} компонента связности, которой принадлежит эта вершина.
{| width = 100%
'''function''' <tex>\mathtt{boruvkaMST}():</tex>
'''while''' <tex>T\mathtt{.size} < n - 1</tex>
'''for''' <tex>k \in </tex> Component <font color = "green">// Component — множество компонент связности в <tex>T</tex></font> <tex>w(\mathtt{minEdge}[k])=\infty</tex> <font color = "green">// для каждой компоненты связности вес минимального ребра = <tex>\infty</tex></font> <tex>\mathtt{findComp(}T\mathtt{)}</tex> <font color = "green">// разбиваем граф <tex>T</tex> на компоненты связности обычным ''dfs''-ом</font>
'''for''' <tex>\mathtt{(u,v)} \in E </tex>
'''if''' <tex>\mathtt{u.comp} \neq \mathtt{v.comp}</tex>
<tex>\mathtt{minEdge}[\mathtt{v.comp}] = (u,v)</tex>
'''for''' <tex>k \in </tex> Component
<tex>T\mathtt{.addEdge}(\mathtt{minEdge}[k])</tex> <font color = "green">// добавляем ребро если его не было в <tex>T</tex></font>
'''return''' <tex>T</tex>
|}
|-
|[[Файл:Boruvka_1.png|250px]]
| <tex>{A}</tex><br/><tex>{B}</tex><br/><tex>{C}</tex><br/><tex>{D}</tex><br/><tex>{E}</tex><br/><tex>{F}</tex><br/><tex>{G}</tex>
|Начальный граф <tex>G</tex>. Каждая вершина является компонентой (синие окружности).
|-
|[[Файл:Boruvka_2.png|250px]]
| <tex>{ABDF}</tex><br/><tex>{CEG}</tex>
|На первой итерации внешнего цикла для каждой компоненты были добавлены минимальные сопряженные ребра. Некоторые ребра добавлены несколько раз (<tex dpi = 120>AD</tex> и <tex dpi = 120>CE</tex>). Осталось две компоненты.
|-
|[[Файл:Boruvka_3.png|250px]]
| <tex>{ABCDEFG}</tex>
|На последней итерации внешнего цикла было добавлено минимальное ребро, соединяющее две оставшиеся компоненты (ребро <tex dpi = 120>BE</tex>). Осталась одна компонента. Минимальное остовное дерево графа <tex dpi = 120>G</tex> построено.
|-
==Асимптотика==
Внешний цикл повторяется <tex>\log{V}</tex> раз, так как количество компонент связности каждый раз уменьшается как минимум в двое (потому что в худшем случае будут объединятся пары компонент) и изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за <tex>E</tex>, где <tex>E</tex> {{---}} количество рёбер в исходном графе. Следовательно конечное время работы алгоритма <tex>O(E\log{V})</tex>.
==См. также==
