Изменения

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

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

Будем последовательно строить подграф Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В <tex>FT</tex> могут быть добавлены все три ребра. Избежать эту проблему можно, например, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером. ==Доказательство корректности== {{Теорема|statement= Алгоритм Борувки строит '''MST'''.|proof=Очевидно, что в результате работы алгоритма получается дерево. Пусть <tex> T </tex> {{---}} минимальное остовное дерево графа <tex>G</tex> ("растущий лес"), поддерживая следующий инвариант: на каждом шаге а <tex>FT' </tex> можно достроить до некоторого MST{{---}} дерево полученное после работы алгоритма. Начнем с того Покажем, что включим в <tex>FT = T'</tex> все вершины графа .  Предположим обратное <tex>GT \neq T' </tex>. Теперь будем обходить множество Пусть ребро <tex>EGe' </tex> в порядке увеличения веса ребер. Добавление очередного ребра {{---}} первое добавленное ребро дерева <tex>eT' </tex> в , не принадлежащее дереву <tex>FT </tex> может привести к возникновению цикла в одной из компонент связности . Пусть <tex>FP </tex>. В этом случае, очевидно{{---}} путь, соединяющий в дереве <tex>eT </tex> не может быть включено в вершины ребра <tex>Fe' </tex>. В противном случае  Понятно, что в момент, когда ребро <tex>e' </tex> соединяет разные компоненты связности добавляли, какое-то ребро <tex>FP </tex>, тогда существует [[Лемма о безопасном ребре#Необходимые определения|разрез]] (назовем его <tex> \langle S, T \rangle e </tex> такой, что одна из компонент связности составляет одну его часть, а оставшаяся часть графа - вторую) не было добавлено. Тогда По алгоритму <tex>w(e) \geqslant w(e') </tex> и есть минимальное ребро, пересекающее этот разрез. Значит, из [[Лемма о безопасном ребре|леммы о безопасном ребре]] следует, что Однако тогда <tex>FT - e +e' </tex> можно продолжить до MST, поэтому добавим это ребро в {{---}} остовное дерево веса не превышающего вес дерева <tex>FT </tex>.Получили противоречение. Следовательно <brtex>T = T'</tex>.Несложно понять, что после выполнения такой процедуры получится остовное дерево, при этом его минимальность вытекает из леммы о безопасном ребре.}}

У вершины есть поле <btex>Вход\mathtt{comp}</btex> {{---}} компонента связности, которой принадлежит эта вершина. {| width = 100%|-| <font color=green>: граф // <tex>G </tex> {{---}} исходный граф</font> <font color= green>// <tex>w</tex> {{---}} весовая функция</font> '''function''' <tex>\mathtt{boruvkaMST}(V, E):</tex> '''while''' <tex>T\mathtt{.size} <brn - 1</tex> '''for''' <btex>Выходk \in </btex>: минимальный остов Component <font color = "green">// Component {{---}} множество компонент связности в <tex>T</tex>. Для </font> <tex>Fw(\mathtt{minEdge}[k])=\infty</tex> графа <font color = "green">// каждой компоненты связности вес минимального ребра = <tex>G\infty</tex>.<br/font>1) <tex>F := \mathtt{findComp(V, }T\varnothingmathtt{)}</tex> <brfont color = "green">// Разбиваем граф <tex>T</tex> на компоненты связности обычным ''dfs''-ом.</font>1) Отсортируем '''for''' <tex>\mathtt{(u,v)} \in E</tex> по весу ребер '''if''' <tex>\mathtt{u.comp} \neq \mathtt{v.comp}<br/tex>2 '''if''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}]) Заведем систему непересекающихся множеств > w(DSUu,v) и инициализируем ее множеством </tex> <tex>V\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)</tex> '''if''' <tex>w(\mathtt{minEdge}[\mathtt{v.comp}]) > w(u,v)<br/tex>3 <tex>\mathtt{minEdge}[\mathtt{v.comp}] = (u,v) Перебирая ребра </tex> '''for''' <tex>uv k \in EG</tex> Component <tex>T\mathtt{.addEdge}(\mathtt{minEdge}[k])</tex> <font color = "green">// Добавляем ребро, если его не было в порядке увеличения веса, смотрим, принадлежат ли <tex>uT</tex> и </font> '''return''' <tex>vT</tex> одному множеству |} ==Пример=={| class = "wikitable"! Изображение !! Компоненты связности !! Описание|-align="center"|[[Файл:Boruvka_1. Если нет, то объединяем множества, в которых лежат png|250px]]| <tex>\{A\}</tex><br/><tex>\{B\}</tex><br/><tex>u\{C\}</tex> и <br/><tex>v\{D\}</tex>, и добавляем ребро <br/><tex>uv\{E\}</tex> к <br/><tex>\{F\}</tex><br/><tex>\{G\}</tex>|Начальный граф <tex>G</tex>.Каждая вершина является компонентой (синие окружности).|-align="center"|[[Файл:Boruvka_2.png|250px]]| <tex>\{ABDF\}</tex><br/><tex>\{CEG\}</tex>|На первой итерации внешнего цикла для каждой компоненты были добавлены минимальные сопряженные ребра. Некоторые ребра добавлены несколько раз (<tex dpi = 120>AD</tex> и <tex dpi = 120>CE</tex>). Осталось две компоненты.|-align="center"|[[Файл:Boruvka_3.png|250px]]| <tex>\{ABCDEFG\}</tex>|На последней итерации внешнего цикла было добавлено минимальное ребро, соединяющее две оставшиеся компоненты (ребро <tex dpi = 120>BE</tex>). Осталась одна компонента. Минимальное остовное дерево графа <tex dpi = 120>G</tex> построено. |-|}

Сортировка На <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 (рус.)