Изменения

Перейти к: навигация, поиск

Обсуждение:PSRS-сортировка

10 098 байт добавлено, 10:53, 3 декабря 2014
Нет описания правки
<b>Алгоритм Борувки</b> (англ. ''Borůvka's algorithm'') — алгоритм поиска минимального остовного дерева (англ. ''minimum spanning tree, MST'') во взвешенном неориентированном связном графе.
Впервые был опубликован в 1926 году Отакаром Борувкой.
==Описание алгоритма==
# Построим граф <tex>T</tex>. Изначально <tex>T</tex> содержит все вершины из <tex>G</tex> и не содержит ребер (каждая вершина в графе <tex>T</tex> {{---}} отдельная компонента связности).
# Будем добавлять в <tex>T</tex> ребра следующим образом, пока <tex>T</tex> не является деревом
#* Для каждой компоненты связности находим минимальное по весу ребро, которое связывает эту компоненту с другой.
#* Добавим в <tex>T</tex> все найденные рёбра.
# Получившийся граф <tex>T</tex> является минимальным остовным деревом графа <tex>G</tex>.
 
Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В <tex>T</tex> могут быть добавлены все три ребра. Избежать эту проблему можно, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.
 
Доказательство будем проводить, считая веса всех ребер различными.
 
==Доказательство корректности==
{{Лемма
|id=lemma1
|statement=Рассмотрим связный неориентированный взвешенный граф <tex> G = (V, E) </tex> с инъективной весовой функцией <tex>w : E \to \mathbb{R}</tex> .
Тогда после первой итерации главного цикла алгоритма Борувки получившийся подграф можно достроить до ''MST''.
|proof=Предположим обратное: пусть любое ''MST'' графа <tex>G</tex> не содержит <tex>T</tex>. Рассмотрим какое-нибудь ''MST''. Тогда существует ребро <tex>x</tex> из <tex>T</tex> такое что <tex>x</tex> не принадлежит ''MST''. Добавив ребро <tex>x</tex> в ''MST'', получаем цикл в котором <tex>x</tex> не максимально, т.к оно было минимальным. Тогда, исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.
}}
 
 
{{Теорема
|id=th1.
|statement=Алгоритм Борувки строит ''MST''.
|proof=Очевидно, что алгоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф <tex>T</tex> можно достроить до ''MST''.
 
Докажем это по индукции.
 
'''База. ''' <tex>n = 1</tex>([[#lemma1|Лемма]]).
 
'''Переход. ''' Пусть лес <tex>T</tex>, получившийся после <tex>n</tex> итераций алгоритма, можно достроить до ''MST''. Докажем, что после <tex>n+1</tex> итерации получившийся лес <tex>T'</tex> можно достроить до ''MST''. Предположим обратное: <tex>T'</tex> нельзя достроить до ''MST''. Тогда существует <tex>F</tex> = ''MST'' графа <tex>G</tex>, содержащее <tex>T</tex> и не содержащее <tex>T'</tex>. Тогда рассмотрим цикл, получающийся добавлением в <tex>F</tex> какого-нибудь ребра <tex>x</tex> из <tex>T' {{---}} T</tex>. На этом цикле имеется ребро, большее по весу чем ребро <tex>x</tex>, иначе компонента для которой <tex>x</tex> является минимальным ребром ни с кем больше ни связана. Исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.
 
'''Получаем. ''' <tex>T'</tex> можно достроить до ''MST''. Следовательно предположение индукции верно.
}}
 
==Реализация==
У вершины есть поле comp — компонента связности, которой принадлежит эта вершина.
 
{| width = 100%
|-
|
<font color=green>// <tex>G</tex> {{---}} исходный граф</font>
<font color=green>// <tex>w</tex> {{---}} весовая функция</font>
'''function''' <tex>\mathtt{burovkaMST}():</tex>
'''while''' <tex>T\mathtt{.size} < n - 1</tex>
'''for''' <tex>k \in </tex> Component // Component — множество компонент связности в T
<tex>w(\mathtt{minEdge}[k])=\infty</tex> // для каждой компоненты связности вес минимального ребра = Inf
<tex>\mathtt{findComp(}T\mathtt{)}</tex> // разбиваеv граф T на компоненты связности обычным dfs-ом
'''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> // добавляем ребро если его не было в T
'''return''' <tex>T</tex>
|}
 
==Пример==
{| class = "wikitable"
! Изображение !! Множество рёбер !! Описание
|-
|[[Файл:Mst_bor_1.png|200px]]
|
|Переберём все вершины и отметим для каждой вершины инцидентное ей ребро минимального веса.
{| width="100%"
|Вершина || '''a''' || '''b''' || '''c''' || '''d''' || '''e'''
|-
|Ребро минимального веса || '''ae''' || '''ab''' || '''cd''' || '''cd''' || '''ae'''
|}
|-
|[[Файл:Mst_bor_2.png|200px]]
|
|Объединим каждую полученную компоненту связности в одну вершину.<br/>
Полученные вершины ''abe'' и ''cd'' соединяют рёбра '''bc''', '''ac''', '''ec''' и '''ed'''.<br/>
Выберем среди них ребро с минимальным весом {{---}} '''ac''' и положим его между полученными вершинами.<br/>
|-
|[[Файл:Mst_bor_3.png|200px]]<br/>[[Файл:Mst_bor_4.png|200px]]
|<center>'''ae''' '''ab''' '''cd'''</center>
|Повторим алгоритм борувки на полученном графе, в результате чего он будет сжат в одну вершину.
|-
|<center>[[Файл:Mst_bor_5.png|80px]]</center>
|<center>'''ae''' '''ab''' '''cd''' '''ac'''</center>
|Граф сжат в одну вершину.<br/>Теперь нужно заменить множество рёбер заданного графа на полученное в алгоритме.
|-
|[[Файл:Mst_bor_6.png|200px]]
|
|Полученный граф {{---}} минимальное остовное дерево заданного графа.
|}
 
==Асимптотика==
Время работы внутри главного цикла будет равно <tex>O(E + V)</tex>.
 
Количество итераций, которое выполняется главным циклом равно <tex>O(\log{V})</tex> так как на каждой итерации количество компонент связности уменьшается в 2 раза (изначально количество компонент равно <tex>|V|</tex>, в итоге должна стать одна компонента).
 
Общее время работы алгоритма получается <tex>O(E\log{V})</tex>.
 
==См. также==
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Алгоритм двух китайцев]]
 
== Ссылки ==
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/mst-2006 Визуализатор алгоритма]
* [http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture11.pdf Minimum Spanning Trees]
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8 Алгоритм Борувки— Википедия]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
Анонимный участник

Навигация