Алгоритм Борувки

Материал из Викиконспекты
Версия от 21:44, 26 сентября 2015; Novik (обсуждение | вклад) (Описание алгоритма)
Перейти к: навигация, поиск

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

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

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

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

Доказательство будем проводить, считая веса всех ребер различными.

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

Лемма:
Рассмотрим связный неориентированный взвешенный граф [math] G = (V, E) [/math] с инъективной весовой функцией [math]w : E \to \mathbb{R}[/math] . Тогда после первой итерации главного цикла алгоритма Борувки получившийся подграф можно достроить до MST.
Доказательство:
[math]\triangleright[/math]
Предположим обратное: пусть любое MST графа [math]G[/math] не содержит [math]T[/math]. Рассмотрим какое-нибудь MST. Тогда существует ребро [math]x[/math] из [math]T[/math] такое что [math]x[/math] не принадлежит MST. Добавив ребро [math]x[/math] в MST, получаем цикл в котором [math]x[/math] не максимально, т.к оно было минимальным. Тогда, исходя из критерия Тарьяна, получаем противоречие.
[math]\triangleleft[/math]


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

Очевидно, что алгоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф [math]T[/math] можно достроить до MST. Докажем это по индукции.

База. [math]n = 1[/math] (см. Лемму).

Переход. Пусть лес [math]T[/math], получившийся после [math]n[/math] итераций алгоритма, можно достроить до MST. Докажем, что после [math]n+1[/math] итерации получившийся лес [math]T'[/math] можно достроить до MST. Предположим обратное: [math]T'[/math] нельзя достроить до MST. Тогда существует [math]F[/math] = MST графа [math]G[/math], содержащее [math]T[/math] и не содержащее [math]T'[/math]. Тогда рассмотрим цикл, получающийся добавлением в [math]F[/math] какого-нибудь ребра [math]x[/math] из [math]T' {{---}} T[/math]. На этом цикле имеется ребро, большее по весу чем ребро [math]x[/math], иначе компонента для которой [math]x[/math] является минимальным ребром ни с кем больше ни связана. Исходя из критерия Тарьяна, получаем противоречие.

Получаем. [math]T'[/math] можно достроить до MST. Следовательно предположение индукции верно.
[math]\triangleleft[/math]

Реализация

У вершины есть поле comp — компонента связности, которой принадлежит эта вершина.

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

Асимптотика

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

См. также

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