В 1926 году чешский математик Отакар Борувка публикует алгоритм объединения городов электросетью: минимальное ребро каждой вершины ищется независимо, поэтому расчёт легко разложить на параллельные потоки. Разбор идёт на графе из пяти вершин – остовное дерево весом 6 собирается за два прохода. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов сравнивают метод с подходами Краскала и Прима на плотных графах.
Электрификация, как и прокладка дорог, требует расчёта: лишний провод стоит денег и времени. Первым решение предложил 27-летний Отакар Борувка, сведя задачу к последовательности шагов. Позже метод переоткрывали Флорек, Перкал и Соллин.
Алгоритм пошагово объединяет вершины: для каждой ищется ребро наименьшего веса, а связанные точки сливаются в компоненту. Повтор шагов даёт минимальное остовное дерево – связку всех точек графа рёбрами наименьшей общей стоимости.
Минимальное остовное дерево не единственное: при равных весах их бывает несколько, а суммарная цена у всех одна. Алгоритму достаточно любого – стоимость сети от выбора не меняется.
Главное достоинство метода – параллельность: компоненты обсчитываются одновременно, каждая своим потоком. Рёбра равного веса алгоритму тоже не мешают – при совпадении берётся первое встреченное.
В отличие от методов Краскала и Прима алгоритм Борувки опирается на систему непересекающихся множеств (DSU): структура помнит, какая вершина в какой компоненте, и подсказывает, что с чем сливать.
Компонента ищет соседа сама: ни очереди с приоритетом, ни отсортированного списка рёбер методу не нужно. Достаточно пройти по всем рёбрам и запомнить минимум для каждой группы точек.
Алгоритм, у которого мало движущихся частей, реже ломается на больших данных.
Разберём на примере. Дан граф из пяти вершин: точки связаны рёбрами с весами от 0 до 8, а числа продублированы матрицей смежности справа (рисунок 1). Рёбра неориентированные – направление не задано, и путь читается в обе стороны.
Рис. 1. Начальный граф: веса рёбер заданы, направления нет
Первый шаг – найти у каждой вершины самое дешёвое ребро. Из точки 0 ведут четыре пути с весами 3, 0, 8 и 7 – дешевле всех выходит 0–2. Тот же перебор повторяется для остальных вершин, и на графе остаются только минимальные рёбра (рисунок 2).
Рис. 2. У каждой вершины подсвечено самое дешёвое ребро
После первого прохода остаются две компоненты: 1–0–2 и 3–4. Соединить их можно четырьмя рёбрами – 0–4, 1–4, 1–3 и 2–3 – с весами 7, 3, 4 и 2. Побеждает то же правило дешевизны: выбирается ребро 2–3 (рисунок 3).
Рис. 3. Компоненты сшивает самое дешёвое из связывающих рёбер
Уберём лишние рёбра – останется минимальное остовное дерево (рисунок 4). Сумма весов уцелевших связей равна 6: дешевле пять городов проводом не соединить. Любое другое дерево на этом графе не выйдет дешевле.
Рис. 4. Минимальное остовное дерево весит 6
Проверить результат легко: в дереве на пяти вершинах ровно четыре ребра. Здесь это 0–2, 0–1, 2–3 и 3–4 – лишнее ребро замкнуло бы цикл, а недостающее оставило бы город без света.
Скорость метода – линейно-логарифмическая:
T = O(E·log V),
где T – время работы, E – количество рёбер, V – число вершин.
По асимптотике Борувка не уступает Краскалу и Приму. Разница в другом: независимый поиск минимальных рёбер раскладывается на потоки, поэтому большой граф метод разбирает быстрее соседей по семейству.
Параллельность даётся не даром: потоки обязаны договориться, какая компонента к какой присоединяется, иначе два ядра сольют одну пару дважды. Синхронизация съедает часть выигрыша, но с ростом графа доля потерь падает.
Какой алгоритм выбрать?
Краскал берут для разреженного графа, где рёбер меньше, чем вершин, а связи заданы списком. Прим выигрывает на плотных графах с матрицей смежности. Борувку выбирают там же, где Прима, но когда расчёт нужно раскидать по потокам.
В чём преимущество Борувки?
Краскал начинает с сортировки всех рёбер, а Прим наращивает единственную компоненту. У Борувки параллелизм встроен: минимальное ребро каждой вершины ищется независимо, поэтому работу делят между ядрами без переделки алгоритма.
Сколько проходов делает алгоритм?
Каждый проход соединяет компоненту хотя бы с одной соседней, поэтому их число падает минимум вдвое. Пять вершин сливаются за два захода, тысяча – за десять, миллион – за двадцать. Отсюда и логарифм в оценке скорости.
Чем опасны равные веса?
Равные веса подводят при небрежном выборе: две компоненты одновременно тянутся друг к другу разными рёбрами и замыкают цикл. Спасает единое правило разрыва ничьей – при совпадении берётся ребро с меньшим номером.
Где Борувка проигрывает?
На одном ядре выигрыш от независимости пропадает: тот же ответ Краскал получает после единственной сортировки, а Прим – одной очередью с приоритетом. Борувку берут ради потоков, а не ради короткого кода.
Для каких задач подойдёт Борувка?
Метод Борувки работает там, где связи важнее точек: сегментация изображений, проектирование оптических линий и транспортных систем, кластеризация и машинное обучение – от тканей мозга до родства штаммов. Расчёты на CPU и GPU опираются на ту же независимость ветвей.
Что запомнить?
Борувка сводит поиск минимального остовного дерева к повтору одного действия: каждая компонента тянется к ближайшему соседу. Пять городов связываются деревом весом 6 за два прохода, миллион – за двадцать. Независимость шагов и делает метод кандидатом на параллельный расчёт.