Изменения

<b>Алгоритм Борувки</b> — (англ. ''Borůvka's algorithm'') {{---}} алгоритм поиска [[Остовные деревья: определения, лемма о безопасном ребре | минимального остовного дерева (minimum spanning tree, MST) ]] во взвешенном неориентированном связном графе.

Пока <tex>F</tex> не является деревом# Для каждой компоненты связанности находим минимальное по весу ребро, которое связывает вершину Алгоритм состоит из данной компоненты с вершиной, не принадлежащей данной компоненте. # Добавим в <tex>F</tex> все ребра, которые хотя бы для одной компоненты оказались минимальными.Получившееся множество <tex>F</tex> является минимальным остовным деревом графа <tex>G</tex>.нескольких шагов:

'''Псевдокод второго прохода:У вершины есть поле <tex>\mathtt{comp}</tex> {{---}} компонента связности, которой принадлежит эта вершина. 

dfs(<font color=green>// <tex>G</tex> {{---}} исходный граф</font> <font color=green>// <tex>w</tex>v, c, parent{{---}} весовая функция</font> '''function''' <tex>\mathtt{boruvkaMST}():</tex> для всех вершин u смежных v:'''while''' <tex>T\mathtt{.size} < n - 1</tex> если ('''for''' <tex>uk \in </tex> родитель) переходим к следующей итерации если (Component <font color = "green">// Component {{---}} множество компонент связности в <tex>uT</tex> не посещена). Для </font> если (<tex>returnw(\mathtt{minEdge}[uk] )=\infty</tex> <font color = enter[v]"green">// каждой компоненты связности вес минимального ребра = <tex>\infty</tex>).</font> <tex>c2 \leftarrowmathtt{findComp(}T\mathtt{)}</tex> новый цвет <font color = "green">// Разбиваем граф <tex>col[vu] \leftarrow c2T</tex> на компоненты связности обычным ''dfs''-ом.</font> dfs( '''for''' <tex>\mathtt{(u, c2, v)} \in E </tex>) иначе '''if''' <tex>col[vu] \leftarrow cmathtt{u.comp} \neq \mathtt{v.comp}</tex> dfs('''if''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}]) > w(u, c, v)</tex>) иначе: если ( <tex>enter\mathtt{minEdge}[\mathtt{u.comp}] <= enter[(u,v])</tex>) '''if''' <tex>colw(\mathtt{minEdge}[vu\mathtt{v.comp}] \leftarrow c) > w(u,v)</tex> start <tex>\mathtt{minEdge}[\mathtt{v.comp}] = (u,v) для всех v вершин графа:</tex> если ('''for''' <tex>vk \in </tex> не посещена)Component dfs<tex>T\mathtt{.addEdge}(\mathtt{minEdge}[k])</tex>v <font color = "green">// Добавляем ребро, -1, -1если его не было в <tex>T</tex></font> '''return''' <tex>T</tex>)

==Пример=={| class = "wikitable"! Изображение !! Компоненты связности !! Описание|-align="center"|[[Файл:Boruvka_1.png|250px]]| <tex>\{A\}<b/tex>Вход<br/b>: граф <tex>G = (V, E)\{B\}</tex><br/><btex>\{C\}</tex>Выход<br/b>: минимальный остов <tex>F\{D\}</tex> графа <br/><tex>G\{E\}</tex><br/>1) <tex>\{F := (V, \varnothing)}</tex><br/>1) Отсортируем <tex>E\{G\}</tex> по весу ребер.<br>2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством |Начальный граф <tex>VG</tex>.<br>Каждая вершина является компонентой (синие окружности).|-align="center"|[[Файл:Boruvka_2.png|250px]]3) Перебирая ребра | <tex>uv \in EG{ABDF\}</tex> в порядке увеличения веса, смотрим, принадлежат ли <br/><tex>u\{CEG\}</tex> и |На первой итерации внешнего цикла для каждой компоненты были добавлены минимальные сопряженные ребра. Некоторые ребра добавлены несколько раз (<texdpi = 120>vAD</tex> одному множеству. Если нет, то объединяем множества, в которых лежат и <texdpi = 120>uCE</tex> и ). Осталось две компоненты.|-align="center"|[[Файл:Boruvka_3.png|250px]]| <tex>v\{ABCDEFG\}</tex>|На последней итерации внешнего цикла было добавлено минимальное ребро, и добавляем соединяющее две оставшиеся компоненты (ребро <texdpi = 120>uvBE</tex> к ). Осталась одна компонента. Минимальное остовное дерево графа <texdpi = 120>FG</tex>построено.<br>|-|}

Сортировка На <tex>Ei </tex> займет -ой итерации внешнего цикла каждая компонента состоит как минимум из двух компонент из <tex>O(E\log Ei - 1)</tex>-й итерации.Значит, на каждой итерации число компонент уменьшается как минимум в <tex> 2 <br/tex>Работа с DSU займет раза. Тогда внешний цикл повторяется <tex>O(E\alpha(log{V})</tex> раз, так как количество компонент изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за <tex>O(E)</tex>, где <tex>\alphaE</tex> {{-- обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу-}} количество рёбер в исходном графе.<br>Алгоритм работает за Следовательно конечное время работы алгоритма <tex>O(E(\log E+\alpha(V))) = O(E\log E) = O(E\log V^2) = O(E\log {V})</tex>. ==Литература==* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)