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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгоритм Борувки - це алгоритм пошуку мінімального кістякового дерева в графі.

Історія[ред.ред. код]

Вперше опубліковано 1926 року Отакаром Борувкою як метод пошуку оптимальної електричної мережі в Моравії. Алгоритм кілька разів був перевідкрито, зокрема Флореком, Перкалєм та Солліном. Останній був єдиним західним ученим з цього переліку, тому алгоритм часто називають алгоритмом Солліна, особливо в літературі з паралельних обчислень.

Алгоритм[ред.ред. код]

Робота алгоритму складається з декількох ітерацій, кожна з яких полягає в послідовному додаванні ребер до кістякового лісу графа, доки ліс не перетвориться на дерево, (тобто, ліс, що складається з однієї компоненти зв'язності).

У псевдокоді, алгоритм можна записати так:

  1. Нехай спочатку T - порожня множина ребер (являє собою ліс, до якого кожна вершина входить як окреме дерево).
  2. Поки T не є деревом (що еквівалентно умові: кількість ребер у T менше, ніж V - 1, де V - кількість вершин у графі):
    • Для кожної компоненти зв'язності (тобто, дерева в кістяковому лісі) у підграфі з ребрами T, знайдемо найдешевше ребро, що пов'язує цю компоненту з будь-якою іншою компонентою зв'язності. Вважаємо, що вага ребер різна, або якось додатково впорядкована так, що завжди можна знайти єдине ребро з мінімальною вагою.
    • Додамо знайдені ребра до множини T.
  3. Отримана множина ребер T є мінімальним кістяковим деревом початкового графа.
Приклад коду:
   Graph Boruvka(Graph G)
      while T.size < n - 1                                   
           init()                                            // для кожної компоненти зв'язності вага мінімального ребра = Inf
           findComp(T)                                       // розбиваємо граф T на компоненти зв'язності звичайним dfs-ом
           for uv \in 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 \in Component                                 // Component — множина компонент зв'язності в T
                   T.addEdge(minEdge[k])                     // додаємо ребро, якщо його не було в T
      return T;

Складність алгоритму[ред.ред. код]

Під час кожної ітерації (за винятком, можливо, останньої) кількість дерев у кістяковому лісі зменшується вдвічі, тому алгоритм зробить не більше, ніж \mathop O (\log V) ітерацій. Кожна ітерація може бути реалізована зі складністю \mathop O (E), тому загальний час роботи алгоритми становить \mathop O (E \log V) (V та E - відповідно кількість вершин та ребер у графі).

Для деяких видів графів, зокрема, планарних, час може бути скорочено до \mathop O (E)[1][2]. Існує також рандомізований алгоритм побудови мінімального кістякового дерева, заснований на алгоритмі Борувки, що працює в середньому за лінійний час.

Див. також[ред.ред. код]

Посилання[ред.ред. код]

  1. Eppstein, David (1999). «Spanning trees and spanners». У Sack, J.-R.; Urrutia, J. Handbook of Computational Geometry. Elsevier. с. 425–461. 
  2. Mareš, Martin (2004). «Two linear time algorithms for MST on minor closed graph classes». Archivum mathematicum 40 (3). с. 315–320.