Алгоритм Борувки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 16 промежуточных версий 1 участника)
Строка 1: Строка 1:
<b>Алгоритм Борувки</b> (англ. ''Borůvka's algorithm'') алгоритм поиска минимального остовного дерева (англ. ''minimum spanning tree, MST'') во взвешенном неориентированном связном графе.
+
<b>Алгоритм Борувки</b> (англ. ''Borůvka's algorithm'') {{---}} алгоритм поиска [[Остовные деревья: определения, лемма о безопасном ребре | минимального остовного дерева]] во взвешенном неориентированном связном графе.
 
Впервые был опубликован в 1926 году Отакаром Борувкой.
 
Впервые был опубликован в 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> могут быть добавлены все три ребра. Избежать эту проблему можно, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.
+
Алгоритм состоит из нескольких шагов:
  
Доказательство будем проводить, считая веса всех ребер различными.
+
# Изначально каждая вершина графа <tex> G </tex >{{---}} тривиальное дерево, а ребра не принадлежат никакому дереву.
 +
# Для каждого дерева <tex> T </tex> найдем минимальное инцидентное ему ребро. Добавим все такие ребра.
 +
# Повторяем шаг <tex> 2 </tex> пока в графе не останется только одно дерево <tex> T </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'''.
|statement=Алгоритм Борувки строит ''MST''.
+
|proof=Очевидно, что в результате работы алгоритма получается дерево. Пусть <tex> T </tex> {{---}} минимальное остовное дерево графа <tex> G </tex>, а <tex> T' </tex> {{---}} дерево полученное после работы алгоритма.
|proof=Очевидно, что алгоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф <tex>T</tex> можно достроить до ''MST''.
 
 
 
Докажем это по индукции.
 
  
'''База. '''  <tex>n = 1</tex>([[#lemma1|Лемма]]).
+
Покажем, что <tex> T = T'</tex>.  
  
'''Переход. '''  Пусть лес <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 \neq T' </tex>. Пусть ребро <tex> e' </tex> {{---}} первое добавленное ребро дерева <tex> T' </tex>, не принадлежащее дереву <tex> T </tex>. Пусть <tex> P </tex> {{---}} путь, соединяющий в дереве <tex> T </tex> вершины ребра <tex> e' </tex>.  
  
'''Получаем. '''  <tex>T'</tex> можно достроить до ''MST''. Следовательно предположение индукции верно.
+
Понятно, что в момент, когда ребро <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>.
 
 
}}
 
}}
  
 
==Реализация==
 
==Реализация==
У вершины есть поле comp компонента связности, которой принадлежит эта вершина.
+
У вершины есть поле <tex>\mathtt{comp}</tex> {{---}} компонента связности, которой принадлежит эта вершина.
  
 
{| width = 100%
 
{| width = 100%
Строка 47: Строка 36:
 
   '''function''' <tex>\mathtt{boruvkaMST}():</tex>
 
   '''function''' <tex>\mathtt{boruvkaMST}():</tex>
 
       '''while''' <tex>T\mathtt{.size} < n - 1</tex>                                   
 
       '''while''' <tex>T\mathtt{.size} < n - 1</tex>                                   
             '''for''' <tex>k \in </tex> Component                                 // Component множество компонент связности в <tex>T</tex>
+
             '''for''' <tex>k \in </tex> Component                             <font color = "green">// Component {{---}} множество компонент связности в <tex>T</tex>. Для </font>
                 <tex>w(\mathtt{minEdge}[k])=\infty</tex>                      // для каждой компоненты связности вес минимального ребра = <tex>\infty</tex>
+
                 <tex>w(\mathtt{minEdge}[k])=\infty</tex>                      <font color = "green">// каждой компоненты связности вес минимального ребра = <tex>\infty</tex>.</font>
             <tex>\mathtt{findComp(}T\mathtt{)}</tex>                                     // разбиваем граф <tex>T</tex> на компоненты связности обычным ''dfs''-ом
+
             <tex>\mathtt{findComp(}T\mathtt{)}</tex>                                 <font color = "green">// Разбиваем граф <tex>T</tex> на компоненты связности обычным ''dfs''-ом.</font>
 
             '''for''' <tex>\mathtt{(u,v)} \in  E </tex>
 
             '''for''' <tex>\mathtt{(u,v)} \in  E </tex>
 
                 '''if''' <tex>\mathtt{u.comp} \neq \mathtt{v.comp}</tex>
 
                 '''if''' <tex>\mathtt{u.comp} \neq \mathtt{v.comp}</tex>
                     '''if''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}]) < w(u,v)</tex>
+
                     '''if''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}]) > w(u,v)</tex>
 
                         <tex>\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)</tex>
 
                         <tex>\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)</tex>
                     '''if''' <tex>w(\mathtt{minEdge}[\mathtt{v.comp}]) < w(u,v)</tex>
+
                     '''if''' <tex>w(\mathtt{minEdge}[\mathtt{v.comp}]) > w(u,v)</tex>
 
                         <tex>\mathtt{minEdge}[\mathtt{v.comp}] = (u,v)</tex>
 
                         <tex>\mathtt{minEdge}[\mathtt{v.comp}] = (u,v)</tex>
 
             '''for''' <tex>k \in </tex> Component                                 
 
             '''for''' <tex>k \in </tex> Component                                 
                 <tex>T\mathtt{.addEdge}(\mathtt{minEdge}[k])</tex>                     // добавляем ребро если его не было в <tex>T</tex>
+
                 <tex>T\mathtt{.addEdge}(\mathtt{minEdge}[k])</tex>                 <font color = "green">// Добавляем ребро, если его не было в <tex>T</tex></font>
 
       '''return''' <tex>T</tex>     
 
       '''return''' <tex>T</tex>     
 
|}
 
|}
Строка 64: Строка 53:
 
{| class = "wikitable"
 
{| class = "wikitable"
 
! Изображение !! Компоненты связности !! Описание
 
! Изображение !! Компоненты связности !! Описание
 +
|-align="center"
 +
|[[Файл: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>. Каждая вершина является компонентой (синие окружности).
 +
|-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> построено.
 
|-
 
|-
|[[Файл:Step_0.png|200px]]
 
|
 
|Начальный граф <tex>T</tex>
 
|-
 
|[[Файл:Step_1.png|200px]]
 
| <center>'''a''' '''b''' '''c''' '''d''' '''e'''</center>
 
|Распределим вершины по компонентам.
 
|-
 
|[[Файл:1step_2.png|200px]]
 
| <center>'''a''' '''b'''  '''c'''  '''d''' '''e'''</center>
 
|Пометим минимальные пути между компонентами.
 
|-
 
|[[Файл:1step_3.png|200px]]<br/>
 
|<center>'''bae'''      '''cd'''</center>
 
|Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу <tex>T</tex><br/>
 
|-
 
|[[Файл:1step_4.png|200px]]
 
|<center>'''bae'''  '''cd'''</center>
 
|Пометим минимальные пути между компонентами.
 
|-
 
|[[Файл:1step_5.png|200px]]
 
|<center>'''baecd'''</center>
 
|Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу <tex>T</tex><br/>
 
 
|}
 
|}
  
 
==Асимптотика==
 
==Асимптотика==
Внешний цикл повторяется <tex>\log{V}</tex> раз, так как количество компонент связности каждый раз уменьшается в двое и изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за <tex>E</tex>, где <tex>E</tex> {{---}} количество рёбер в исходном графе. Следовательно конечное время работы алгоритма <tex>O(E\log{V})</tex>.
+
На <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>.
  
 
==См. также==
 
==См. также==
Строка 98: Строка 76:
 
* [[Алгоритм двух китайцев]]
 
* [[Алгоритм двух китайцев]]
  
== Ссылки ==
+
== Источники информации ==
 
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/mst-2006 Визуализатор алгоритма]
 
* [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://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture11.pdf Minimum Spanning Trees]

Версия 20:42, 1 сентября 2019

Алгоритм Борувки (англ. Borůvka's algorithm) — алгоритм поиска минимального остовного дерева во взвешенном неориентированном связном графе. Впервые был опубликован в 1926 году Отакаром Борувкой.

Описание алгоритма

Алгоритм состоит из нескольких шагов:

  1. Изначально каждая вершина графа [math] G [/math]— тривиальное дерево, а ребра не принадлежат никакому дереву.
  2. Для каждого дерева [math] T [/math] найдем минимальное инцидентное ему ребро. Добавим все такие ребра.
  3. Повторяем шаг [math] 2 [/math] пока в графе не останется только одно дерево [math] T [/math].


Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В [math]T[/math] могут быть добавлены все три ребра. Избежать эту проблему можно, например, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.

Доказательство корректности

Теорема:
Алгоритм Борувки строит MST.
Доказательство:
[math]\triangleright[/math]

Очевидно, что в результате работы алгоритма получается дерево. Пусть [math] T [/math] — минимальное остовное дерево графа [math] G [/math], а [math] T' [/math] — дерево полученное после работы алгоритма.

Покажем, что [math] T = T'[/math].

Предположим обратное [math] T \neq T' [/math]. Пусть ребро [math] e' [/math] — первое добавленное ребро дерева [math] T' [/math], не принадлежащее дереву [math] T [/math]. Пусть [math] P [/math] — путь, соединяющий в дереве [math] T [/math] вершины ребра [math] e' [/math].

Понятно, что в момент, когда ребро [math] e' [/math] добавляли, какое-то ребро [math] P [/math] (назовем его [math] e [/math]) не было добавлено. По алгоритму [math] w(e) \geqslant w(e') [/math]. Однако тогда [math] T - e + e' [/math] — остовное дерево веса не превышающего вес дерева [math] T [/math]. Получили противоречение. Следовательно [math] T = T'[/math].
[math]\triangleleft[/math]

Реализация

У вершины есть поле [math]\mathtt{comp}[/math] — компонента связности, которой принадлежит эта вершина.

  // [math]G[/math] — исходный граф
  // [math]w[/math] — весовая функция
  function [math]\mathtt{boruvkaMST}():[/math]
      while [math]T\mathtt{.size} \lt  n - 1[/math]                                   
           for [math]k \in [/math] Component                             // Component — множество компонент связности в [math]T[/math]. Для 
               [math]w(\mathtt{minEdge}[k])=\infty[/math]                      // каждой компоненты связности вес минимального ребра = [math]\infty[/math].
           [math]\mathtt{findComp(}T\mathtt{)}[/math]                                 // Разбиваем граф [math]T[/math] на компоненты связности обычным dfs-ом.
           for [math]\mathtt{(u,v)} \in  E [/math]
               if [math]\mathtt{u.comp} \neq \mathtt{v.comp}[/math]
                   if [math]w(\mathtt{minEdge}[\mathtt{u.comp}]) \gt  w(u,v)[/math]
                       [math]\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)[/math]
                   if [math]w(\mathtt{minEdge}[\mathtt{v.comp}]) \gt  w(u,v)[/math]
                       [math]\mathtt{minEdge}[\mathtt{v.comp}] = (u,v)[/math]
           for [math]k \in [/math] Component                                 
               [math]T\mathtt{.addEdge}(\mathtt{minEdge}[k])[/math]                  // Добавляем ребро, если его не было в [math]T[/math]
      return [math]T[/math]     

Пример

Изображение Компоненты связности Описание
Boruvka 1.png [math]\{A\}[/math]
[math]\{B\}[/math]
[math]\{C\}[/math]
[math]\{D\}[/math]
[math]\{E\}[/math]
[math]\{F\}[/math]
[math]\{G\}[/math]
Начальный граф [math]G[/math]. Каждая вершина является компонентой (синие окружности).
Boruvka 2.png [math]\{ABDF\}[/math]
[math]\{CEG\}[/math]
На первой итерации внешнего цикла для каждой компоненты были добавлены минимальные сопряженные ребра. Некоторые ребра добавлены несколько раз ([math]AD[/math] и [math]CE[/math]). Осталось две компоненты.
Boruvka 3.png [math]\{ABCDEFG\}[/math] На последней итерации внешнего цикла было добавлено минимальное ребро, соединяющее две оставшиеся компоненты (ребро [math]BE[/math]). Осталась одна компонента. Минимальное остовное дерево графа [math]G[/math] построено.

Асимптотика

На [math] i [/math]-ой итерации внешнего цикла каждая компонента состоит как минимум из двух компонент из [math] (i - 1) [/math]-й итерации. Значит, на каждой итерации число компонент уменьшается как минимум в [math] 2 [/math] раза. Тогда внешний цикл повторяется [math]O(\log{V})[/math] раз, так как количество компонент изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за [math]O(E)[/math], где [math]E[/math] — количество рёбер в исходном графе. Следовательно конечное время работы алгоритма [math]O(E\log{V})[/math].

См. также

Источники информации