Алгоритм Борувки - Preparation to IOI Part 3

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

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

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

Алгоритм Борувки строит минимальное остовное дерево раундами.
В каждом раунде каждая компонента выбирает самое дешёвое ребро, ведущее в другую компоненту, и все такие рёбра одновременно добавляются в MST.

Идея алгоритма

Изначально каждая вершина — отдельная компонента.
В одном раунде каждая компонента:
- находит минимальное исходящее ребро;
- добавляет его в MST.
После этого компоненты объединяются.
Количество компонент уменьшается как минимум вдвое, поэтому раундов всего $O(\log V)$ .

Шаги алгоритма

Инициализация
Каждая вершина образует собственную компоненту.
Один раунд
- Для каждой компоненты найти минимальное ребро, соединяющее её с другой компонентой.
- Добавить все найденные рёбра в MST.
- Объединить компоненты, соединённые этими рёбрами.
Повторение
Повторять раунды, пока не останется одна компонента.
Результат
Все добавленные рёбра образуют минимальное остовное дерево.

Визуализация

Сложность

Каждый раунд: перебор всех рёбер — $O (E)$

O(E)

struct Edge {
    int u, v, weight;
};

int n;                 // количество вершин
vector<Edge> edges;    // список рёбер

vector<Edge> boruvka() {
    DSU dsu(n);
    vector<Edge> mst;
    int components = n;

    while (components > 1) {
        vector<int> best_edge(n, -1);

        // ищем минимальное исходящее ребро для каждой компоненты
        for (int i = 0; i < (int)edges.size(); i++) {
            int u = dsu.find_set(edges[i].u);
            int v = dsu.find_set(edges[i].v);
            if (u == v) continue;

            if (best_edge[u] == -1 || edges[i].weight < edges[best_edge[u]].weight) {
                best_edge[u] = i;
            }
            if (best_edge[v] == -1 || edges[i].weight < edges[best_edge[v]].weight) {
                best_edge[v] = i;
            }
        }

        // добавляем найденные рёбра
        for (int i = 0; i < n; i++) {
            if (best_edge[i] == -1) continue;

            Edge e = edges[best_edge[i]];
            int u = dsu.find_set(e.u);
            int v = dsu.find_set(e.v);
            if (u == v) continue;

            mst.push_back(e);
            dsu.union_sets(u, v);
            components--;
        }
    }

    return mst;
}