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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Асимптотика)
(Реализация)
Строка 28: Строка 28:
 
       return T;     
 
       return T;     
 
|}
 
|}
 
<b>Вход</b>: граф <tex>G = (V, E)</tex><br>
 
<b>Выход</b>: минимальный остов <tex>F</tex> графа <tex>G</tex><br>
 
1) <tex>F := (V, \varnothing)</tex><br>
 
1) Отсортируем <tex>E</tex> по весу ребер.<br>
 
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством <tex>V</tex>.<br>
 
3) Перебирая ребра <tex>uv \in EG</tex> в порядке увеличения веса, смотрим, принадлежат ли <tex>u</tex> и <tex>v</tex> одному множеству. Если нет, то объединяем множества, в которых лежат <tex>u</tex> и <tex>v</tex>, и добавляем ребро <tex>uv</tex> к <tex>F</tex>.<br>
 
  
 
==Асимптотика==
 
==Асимптотика==

Версия 02:25, 15 декабря 2012

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

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

Пока [math]T[/math] не является деревом

  1. Для каждой компоненты связанности находим минимальное по весу ребро, которое связывает вершину из данной компоненты с вершиной, не принадлежащей данной компоненте.
  2. Добавим в [math]T[/math] все ребра, которые хотя бы для одной компоненты оказались минимальными.

Получившееся множество [math]T[/math] является минимальным остовным деревом графа [math]G[/math].

Реализация

  Graph Boruvka(Graph G)
      while T.size < n
           init()                                            // у вершины есть поле comp(компонента которой принадлежит вершина) 
           findComp(T)                                       // разбивает граф T на компоненты связынности обычным dfs-ом
           for uv [math]\in[/math] E
               if u.comp != v.comp
                   if minEdge[u.comp].w < uv.w
                       minEdge[u.comp] = uv
                   if minEdge[v.comp].w < uv.w
                       minEdge[v.comp] = uv)
           for k [math]\in[/math] K                                         // K - множество компонент связанности в T
                   T.addEdge(minEdge[k])
            
      return T;     

Асимптотика

Время работы внутри главного цикла будет равно [math]O(E + V)[/math] + [math]O(E)[/math] + [math]O(V)[/math] = [math]O(E)[/math].

Количество итераций которое выполняется главным циклом = [math]O(\log{V})[/math] т.к на каждой итерации количество компонент связанности уменьшается в 2 раза.

Литература

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

См. также