Arbore parțial minim: Prim, Kruskal și DSU

Un arbore parțial de cost minim conectează toate vârfurile unui graf neorientat conex folosind n-1 muchii, fără cicluri și cu sumă minimă a costurilor. Kruskal și Prim construiesc acest arbore prin alegeri greedy, dar organizează diferit candidații.

Problema nu cere cel mai scurt drum dintre două vârfuri. Minimizăm costul total al conexiunilor păstrate, iar drumul dintre o anumită pereche în arbore poate fi mai scump decât drumul minim din graful inițial.

Cum funcționează

Kruskal și mulțimile disjuncte

Kruskal sortează muchiile crescător după cost. Acceptă o muchie dacă extremitățile ei se află în componente diferite ale pădurii construite până atunci. Dacă sunt deja conectate, muchia ar închide un ciclu și este respinsă. Structura DSU, numită și union-find, menține această partiție în componente.

În DSU, fiecare element are un părinte, iar reprezentantul unei componente este o rădăcină care se indică pe sine. Funcția root comprimă drumul, conectând elementele vizitate direct la reprezentant. unite atașează componenta mai mică celei mai mari. Dimensiunea sz se actualizează numai la noua rădăcină; ea nu este gradul vârfului în graful original. Dacă reprezentanții coincid, nu unim din nou.

Prim și muchia care extinde arborele

Prim pornește dintr-un vârf și păstrează pentru fiecare vârf exterior cea mai ieftină muchie care îl conectează la mulțimea deja selectată. Alege minimul acestor costuri, adaugă vârful și actualizează candidații. Valoarea best este costul unei singure muchii de legătură, nu distanța acumulată de la start, cum ar fi în Dijkstra.

Programele presupun 1 <= n <= 100, 0 <= m <= 10000, fără bucle și costuri cu modulul cel mult un milion. Sunt acceptate muchii paralele; matricea Prim păstrează minimul lor. Tablourile clasice folosesc indicii 1..n pentru vârfuri și 0..m-1 pentru muchii. Variantele vector păstrează limitele. Pentru sortarea vectorului folosim iteratorii begin(), în locul pointerilor e și e+m.

Exemplu urmărit pas cu pas

Pentru muchiile 1-2 de cost 1, 2-3 de cost 2, 3-4 de cost 3 și 1-4 de cost 10, Kruskal acceptă primele trei. Ultima ar închide un ciclu. Costul total este 6.

Prim pornit din 1 alege legătura către 2, apoi către 3 și apoi către 4, obținând același cost. În grafuri cu egalități, cei doi algoritmi pot produce arbori diferiți, dar cu același cost optim. Dacă nu pot conecta toate vârfurile, programele afișează NECONEX, fără să numească pădurea rezultată arbore parțial al întregului graf.

Implementare C++17

Kruskal: tablou clasic

#include <algorithm>
#include <iostream>
struct Edge {
    int u, v;
    long long w;
};
Edge e[10000];
int parent[101], sz[101];
int root(int x) {
    if (parent[x] != x)
        parent[x] = root(parent[x]);
    return parent[x];
}
bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y)
        return false;
    if (sz[x] < sz[y])
        std::swap(x, y);
    parent[y] = x;
    sz[x] += sz[y];
    return true;
}
int main() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        sz[i] = 1;
    }
    for (int i = 0; i < m; ++i)
        std::cin >> e[i].u >> e[i].v >> e[i].w;
    std::sort(e, e + m, [](const Edge &a, const Edge &b) { return a.w < b.w; });
    int used = 0;
    long long total = 0;
    for (int i = 0; i < m; ++i)
        if (unite(e[i].u, e[i].v)) {
            total += e[i].w;
            ++used;
        }
    if (used != n - 1)
        std::cout << "NECONEX\n";
    else
        std::cout << total << '\n';
}

Kruskal: std::vector

#include <algorithm>
#include <iostream>
#include <vector>
struct Edge {
    int u, v;
    long long w;
};
std::vector<Edge> e(10000);
std::vector<int> parent(101), sz(101);
int root(int x) {
    if (parent[x] != x)
        parent[x] = root(parent[x]);
    return parent[x];
}
bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y)
        return false;
    if (sz[x] < sz[y])
        std::swap(x, y);
    parent[y] = x;
    sz[x] += sz[y];
    return true;
}
int main() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        sz[i] = 1;
    }
    for (int i = 0; i < m; ++i)
        std::cin >> e[i].u >> e[i].v >> e[i].w;
    std::sort(e.begin(), e.begin() + m,
              [](const Edge &a, const Edge &b) { return a.w < b.w; });
    int used = 0;
    long long total = 0;
    for (int i = 0; i < m; ++i)
        if (unite(e[i].u, e[i].v)) {
            total += e[i].w;
            ++used;
        }
    if (used != n - 1)
        std::cout << "NECONEX\n";
    else
        std::cout << total << '\n';
}

Prim

Varianta cu tablou clasic:

#include <algorithm>
#include <iostream>
const long long INF = 4000000000000000000LL;
int main() {
    int n, m;
    std::cin >> n >> m;
    long long a[101][101], best[101];
    bool used[101] = {};
    for (int i = 1; i <= n; ++i) {
        best[i] = INF;
        for (int j = 1; j <= n; ++j)
            a[i][j] = INF;
    }
    for (int i = 0; i < m; ++i) {
        int x, y;
        long long w;
        std::cin >> x >> y >> w;
        a[x][y] = a[y][x] = std::min(a[x][y], w);
    }
    best[1] = 0;
    long long total = 0;
    for (int step = 0; step < n; ++step) {
        int x = 0;
        for (int i = 1; i <= n; ++i)
            if (!used[i] && (x == 0 || best[i] < best[x]))
                x = i;
        if (best[x] == INF) {
            std::cout << "NECONEX\n";
            return 0;
        }
        used[x] = true;
        total += best[x];
        for (int y = 1; y <= n; ++y)
            if (!used[y] && a[x][y] < best[y])
                best[y] = a[x][y];
    }
    std::cout << total << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <algorithm>
#include <iostream>
#include <vector>
const long long INF = 4000000000000000000LL;
int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<long long>> a(n + 1, std::vector<long long>(n + 1));
    std::vector<long long> best(n + 1);
    std::vector<char> used(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        best[i] = INF;
        for (int j = 1; j <= n; ++j)
            a[i][j] = INF;
    }
    for (int i = 0; i < m; ++i) {
        int x, y;
        long long w;
        std::cin >> x >> y >> w;
        a[x][y] = a[y][x] = std::min(a[x][y], w);
    }
    best[1] = 0;
    long long total = 0;
    for (int step = 0; step < n; ++step) {
        int x = 0;
        for (int i = 1; i <= n; ++i)
            if (!used[i] && (x == 0 || best[i] < best[x]))
                x = i;
        if (best[x] == INF) {
            std::cout << "NECONEX\n";
            return 0;
        }
        used[x] = true;
        total += best[x];
        for (int y = 1; y <= n; ++y)
            if (!used[y] && a[x][y] < best[y])
                best[y] = a[x][y];
    }
    std::cout << total << '\n';
}

De ce funcționează și cât costă

Proprietatea tăieturii justifică alegerile: o muchie de cost minim care traversează o separare potrivită între componente poate fi inclusă într-un arbore optim. Dacă un arbore optim folosește altă muchie pentru acea legătură, schimbul păstrează conexitatea și nu crește costul.

Kruskal costă O(m log m) pentru sortare, plus operațiile DSU aproape constante amortizat cu ambele optimizări; memoria este O(n+m). Prim cu matrice costă O(n²+m) timp și O(n²) memorie. O variantă Prim cu liste și coadă de priorități este utilă pentru grafuri rare, dar nu este implementarea de aici.

Greșeli frecvente

Nu confunda DSU cu lista muchiilor arborelui: părinții DSU sunt administrativi. Nu uita testul de conexitate. Costurile negative sunt permise pentru această problemă. Egalitatea costurilor poate duce la mai multe soluții optime, fără să invalideze algoritmul.

Exersează

Într-un triunghi cu toate costurile egale cu 2, câți arbori minimi există și care este costul fiecăruia?

Rezolvare explicată: Oricare două dintre cele trei muchii formează un arbore. Există trei alegeri, fiecare cu suma 4. Costul optim nu implică unicitatea arborelui.

Continuă să înveți

Arbori, greedy și sortare.

Întrebări frecvente

Arborele minim conține drumurile minime dintre toate perechile?

Nu. El minimizează suma muchiilor păstrate pentru conectarea tuturor vârfurilor. Aceasta este o altă funcție obiectiv decât distanța unei perechi.

De ce are n-1 muchii?

Orice arbore cu n vârfuri are n-1 muchii. Conectarea componentelor fără a crea cicluri reduce numărul componentelor cu unu la fiecare muchie acceptată.

Ce păstrează DSU?

Partiția elementelor în mulțimi disjuncte și un reprezentant pentru fiecare. Părinții săi nu reprezintă neapărat muchiile arborelui minim.

Pot exista costuri negative?

Da. Kruskal și Prim rămân valizi pentru costuri negative în problema arborelui parțial minim neorientat.

Ce fac dacă graful este neconex?

Nu există un arbore care să includă toate vârfurile folosind numai muchiile grafului. Poți cere separat o pădure minimă, dar aceasta este o altă formulare a rezultatului.