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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
(Реализация)
Строка 15: Строка 15:
 
|-
 
|-
 
|  
 
|  
   Boruvka(<tex>G</tex>)
+
   Graph Boruvka(Graph G)
 
        
 
        
       while T.size < n
+
       while (T.size < n)
             for (uv принадлежащим E)  
+
             for (uv <tex>\in</tex> E)  
 
                 if (u.color != v.color)
 
                 if (u.color != v.color)
                     if (min_edge[u.color] < uv.w)
+
                     if (minEdge[u.color] < uv.w)
                         min_edge[u.color] = uv.w
+
                         minEdge[u.color] = uv.w
                     if (min_edge[v.color] < uv.w)
+
                     if (minEdge[v.color] < uv.w)
                         min_edge[v.color] = uv.w)
+
                         minEdge[v.color] = uv.w)
              
+
             for (color)
 +
                T.addEdge(minEdge[color])
 +
            for (u <tex>\in</tex> G)
 +
                dfs(u, color++)
 +
           
 +
      return T;   
 
|}
 
|}
  

Версия 01:10, 15 декабря 2012

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

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

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

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

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


Реализация

  Graph Boruvka(Graph G)
      
      while (T.size < n)
           for (uv [math]\in[/math] E) 
               if (u.color != v.color)
                   if (minEdge[u.color] < uv.w)
                       minEdge[u.color] = uv.w
                   if (minEdge[v.color] < uv.w)
                       minEdge[v.color] = uv.w)
           for (color)
               T.addEdge(minEdge[color])
           for (u [math]\in[/math] G)
               dfs(u, color++)
            
      return T;     

Вход: граф [math]G = (V, E)[/math]
Выход: минимальный остов [math]F[/math] графа [math]G[/math]
1) [math]F := (V, \varnothing)[/math]
1) Отсортируем [math]E[/math] по весу ребер.
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством [math]V[/math].
3) Перебирая ребра [math]uv \in EG[/math] в порядке увеличения веса, смотрим, принадлежат ли [math]u[/math] и [math]v[/math] одному множеству. Если нет, то объединяем множества, в которых лежат [math]u[/math] и [math]v[/math], и добавляем ребро [math]uv[/math] к [math]F[/math].

Асимптотика

Сортировка [math]E[/math] займет [math]O(E\log E)[/math].
Работа с DSU займет [math]O(E\alpha(V))[/math], где [math]\alpha[/math] - обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу.
Алгоритм работает за [math]O(E(\log E+\alpha(V))) = O(E\log E) = O(E\log V^2) = O(E\log V)[/math].

Литература

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

См. также