Алгоритм Борувки — це алгоритм пошуку мінімального кістякового дерева в графі.
Історія Вперше опубліковано 1926 року Отакаром Борувкою як метод пошуку оптимальної електричної мережі в Моравії. Алгоритм кілька разів було перевідкрито, зокрема Флореком, Перкалєм та Солліном. Останній був єдиним західним ученим з цього переліку, тому алгоритм часто називають алгоритмом Солліна, особливо в літературі з паралельних обчислень.
Алгоритм
Робота алгоритму складається з декількох ітерацій, кожна з яких полягає в послідовному додаванні ребер до кістякового лісу графу, доки ліс не перетвориться на дерево, (тобто, ліс, що складається з однієї компоненти зв'язності).
У псевдокоді, алгоритм можна записати так: Нехай спочатку T — порожня множина ребер (являє собою ліс, до якого кожна вершина входить як окреме дерево). Поки T не є деревом (що еквівалентно умові: кількість ребер у T менше, ніж V — 1, де V — кількість вершин у графі): Для кожної компоненти зв'язності (тобто, дерева в кістяковому лісі) у підграфі з ребрами T, знайдемо найдешевше ребро, що пов'язує цю компоненту з будь-якою іншою компонентою зв'язності. Вважаємо, що вага ребер різна, або якось додатково впорядкована так, що завжди можна знайти єдине ребро з мінімальною вагою. Додамо знайдені ребра до множини T. Отримана множина ребер 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;
Складність алгоритму
Під час кожної ітерації (за винятком, можливо, останньої) кількість дерев у кістяковому лісі зменшується вдвічі, тому алгоритм зробить не більше, ніж ітерацій. Кожна ітерація може бути реалізована зі складністю , тому загальний час роботи алгоритми становить (V та E — відповідно кількість вершин та ребер у графі).
Для деяких видів графів, зокрема, планарних, час може бути скорочено до . Існує також рандомізований алгоритм побудови мінімального кістякового дерева, заснований на алгоритмі Борувки, що працює в середньому за лінійний час.
Див. також Алгоритм Крускала Алгоритм Прима
Посилання