1632
правки
Изменения
м
Внешний На <tex> i </tex>-ой итерации внешнего цикла каждая компонента состоит как минимум из двух компонент из <tex> (i - 1) </tex>-й итерации. Значит, на каждой итерации число компонент уменьшается как минимум в <tex> 2 </tex> раза. Тогда внешний цикл повторяется <tex>O(\log{V})</tex> раз, так как количество компонент связности каждый раз уменьшается как минимум в двое(потому что в худшем случае будут объединятся пары компонент) и изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за <tex>O(E)</tex>, где <tex>E</tex> {{---}} количество рёбер в исходном графе. Следовательно конечное время работы алгоритма <tex>O(E\log{V})</tex>.
rollbackEdits.php mass rollback
==Описание алгоритма==
Алгоритм состоит из нескольких шагов:
# Изначально каждая вершина графа <tex> G </tex >{{---}} тривиальное дерево, а ребра не принадлежат никакому дереву.
# Для каждого дерева <tex> T </tex> найдем минимальное инцидентное ему ребро. Добавим все такие ребра.
{{Теорема
|statement= Алгоритм Борувки строит '''MST'''.
|proof=Очевидно, что в результате работы алгоритма получается дерево. Пусть <tex> T </tex> {{---}} минимальное остовное дерево графа <tex> G </tex>, а <tex> T' </tex> {{---}} дерево полученное после работы алгоритма.
Покажем, что <tex> T = T'</tex>.
Предположим обратное <tex> T \neq T' </tex>. Пусть ребро <tex> e' </tex> {{---}} первое окрашенное добавленное ребро дерева <tex> T' </tex>, не принадлежащее дереву <tex> T </tex>. Пусть <tex> P </tex> {{---}} путь, соединяющий в дереве <tex> T </tex> вершины ребра <tex> e' </tex>.
Понятно, что в момент, когда ребро <tex> e' </tex> красилидобавляли, какое-то ребро <tex> P </tex> (назовем его <tex> e </tex>) не было покрашенодобавлено. По алгоритму <tex> w(e) \geqslant w(e') </tex>. Однако тогда <tex> T - e + e' </tex> {{---}} остовное дерево веса не превышающего вес дерева <tex> T </tex>. Получили противоречение. Следовательно <tex> T = T'</tex>.
}}
'''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>
'''if''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}]) < > w(u,v)</tex>
<tex>\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)</tex>
'''if''' <tex>w(\mathtt{minEdge}[\mathtt{v.comp}]) < > w(u,v)</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>
|}
==Асимптотика==
==См. также==
