Алгоритми Борувка - Course 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;
}