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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Пример)
Строка 50: Строка 50:
 
{| class = "wikitable"
 
{| class = "wikitable"
 
! Изображение !! Компоненты связности !! Описание
 
! Изображение !! Компоненты связности !! Описание
|-
+
|-align="center"
 
|[[Файл:Boruvka_1.png|250px]]
 
|[[Файл: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>{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>. Каждая вершина является компонентой (синие окружности).
 
|Начальный граф <tex>G</tex>. Каждая вершина является компонентой (синие окружности).
|-
+
|-align="center"
 
|[[Файл:Boruvka_2.png|250px]]
 
|[[Файл:Boruvka_2.png|250px]]
 
| <tex>{ABDF}</tex><br/><tex>{CEG}</tex>
 
| <tex>{ABDF}</tex><br/><tex>{CEG}</tex>
 
|На первой итерации внешнего цикла для каждой компоненты были добавлены минимальные сопряженные ребра. Некоторые ребра добавлены несколько раз (<tex dpi = 120>AD</tex> и <tex dpi = 120>CE</tex>). Осталось две компоненты.
 
|На первой итерации внешнего цикла для каждой компоненты были добавлены минимальные сопряженные ребра. Некоторые ребра добавлены несколько раз (<tex dpi = 120>AD</tex> и <tex dpi = 120>CE</tex>). Осталось две компоненты.
|-
+
|-align="center"
 
|[[Файл:Boruvka_3.png|250px]]
 
|[[Файл:Boruvka_3.png|250px]]
 
| <tex>{ABCDEFG}</tex>
 
| <tex>{ABCDEFG}</tex>

Версия 19:28, 11 октября 2015

Алгоритм Борувки (англ. 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}]) \lt  w(u,v)[/math]
                       [math]\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)[/math]
                   if [math]w(\mathtt{minEdge}[\mathtt{v.comp}]) \lt  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]\log{V}[/math] раз, так как количество компонент связности каждый раз уменьшается как минимум в двое(потому что в худшем случае будут объединятся пары компонент) и изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за [math]E[/math], где [math]E[/math] — количество рёбер в исходном графе. Следовательно конечное время работы алгоритма [math]O(E\log{V})[/math].

См. также

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