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

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

Історія

Вперше опубліковано 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; 

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

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

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

Див. також

• Алгоритм Крускала
• Алгоритм Прима

Посилання

1. Eppstein, David (1999). Spanning trees and spanners. У Sack, J.-R.; Urrutia, J. (ред.). Handbook of Computational Geometry. Elsevier. с. 425—461.
2. Mareš, Martin (2004). (PDF). Т. 40, № 3. с. 315—320. Архів оригіналу (PDF) за 9 травня 2009. Процитовано 22 січня 2011. {{}}: Проігноровано |journal= ()