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

Прим растит одну компоненту, Краскал перебирает рёбра. Борувка обрабатывает все компоненты сразу.

Итерация: для каждой текущей компоненты находим минимальное ребро, ведущее наружу, и добавляем все найденные рёбра разом. Повторяем, пока компонента не останется одна.

DSU dsu(n);
long long total = 0;
int comps = n;
while (comps > 1) {
    vector<int> bestEdge(n, -1);
    for (int i = 0; i < (int)edges.size(); i++) {
        auto [u, v, w] = edges[i];
        int a = dsu.get(u), b = dsu.get(v);
        if (a == b) continue;
        if (bestEdge[a] == -1 || w < edges[bestEdge[a]].w) bestEdge[a] = i;
        if (bestEdge[b] == -1 || w < edges[bestEdge[b]].w) bestEdge[b] = i;
    }
    bool any = false;
    for (int v = 0; v < n; v++)
        if (bestEdge[v] != -1) {
            auto [a, b, w] = edges[bestEdge[v]];
            if (dsu.unite(a, b)) { total += w; comps--; any = true; }
        }
    if (!any) break;                       // граф несвязен
}

Проверено: на 40 000 графов результат совпал с перебором всех остовных подмножеств рёбер.

Почему итераций логарифм

Каждая компонента на итерации объединяется хотя бы с одной другой. Значит, число компонент уменьшается хотя бы вдвое: даже в худшем случае они разбиваются на пары.

Начали с $n$ компонент, каждая итерация делит их число пополам — итераций не больше $\log_2 n$. Каждая стоит $O(m)$ на просмотр рёбер, итого $O(m \log n)$.

Аккуратность с одинаковыми весами

Если две компоненты выбрали друг друга, ребро добавится дважды. В коде выше это гасит unite, возвращающая false на втором вызове.

Хуже другое: при одинаковых весах может получиться цикл из трёх и более компонент, каждая выбрала следующую. Тогда unite спасёт не полностью, и в дерево попадёт лишнее ребро.

Стандартное лечение — сделать веса попарно различными искусственно: сравнивать пары (вес, номер ребра). Тогда «минимальное ребро» определено однозначно и циклов выбора не возникает.

Зачем он нужен

На практике Прим и Краскал проще и обычно быстрее. Борувка ценен другим.

Параллелится. Компоненты выбирают рёбра независимо — работу можно раздать потокам. Прим по своей природе последовательный.

Не требует сортировки и очереди. Только проходы по списку рёбер и СНМ.

Основа для более быстрых алгоритмов. Известные алгоритмы построения МОД за $O(m \alpha(m, n))$ и линейные рандомизированные строятся на итерации Борувки как на кирпиче.

Работает на неявном графе. Если рёбер квадратично много, но минимальное исходящее ребро компоненты умеет находиться быстро (например, геометрически), Борувка не требует их перечислять — а Краскалу нужен весь список.