Arbore parțial de cost minim

Intuiția

Pornești de la un graf ponderat conex: nodurile sunt satele, muchiile sunt tronsoanele posibile, iar costul fiecărei muchii e prețul cablului. Cauți o submulțime de muchii care leagă toate nodurile și are suma costurilor cea mai mică.

Dacă păstrezi o muchie în plus față de strictul necesar, ai creat un ciclu — adică un tronson care leagă două sate deja conectate pe altă cale. Acel tronson e bani aruncați: îl poți tăia fără să deconectezi pe nimeni. O rețea conexă fără niciun ciclu se numește arbore, iar cea mai ieftină dintre toate se numește arbore parțial de cost minim (APM).

Vezi cum funcționează

Urmărește cum se construiește rețeaua: muchiile sunt luate în considerare în ordinea crescătoare a costului, iar o muchie e adăugată doar dacă nu închide un ciclu. La final rămâne un arbore care atinge toate nodurile cu cost total minim.

Algoritmul pas cu pas

Fie un graf cu 4 noduri și 5 muchii cu costurile: (1,2)=1, (2,3)=2, (1,3)=3, (3,4)=4, (2,4)=5.

Întâi sortăm muchiile crescător după cost și le parcurgem în ordine. Pentru fiecare ne întrebăm doar atât: capetele sunt deja conectate prin muchiile alese? Dacă nu, o acceptăm; dacă da, am face ciclu, deci o respingem.

Pas cu pas pe lista sortată:

• Costul 1, muchia (1,2): nodurile 1 și 2 nu erau conectate. Acceptăm. Avem 1 muchie.
• Costul 2, muchia (2,3): 3 nu era încă în rețea. Acceptăm. Avem 2 muchii; acum 1, 2, 3 sunt toate conectate.
• Costul 3, muchia (1,3): 1 și 3 sunt deja conectate (prin 2). Ar închide un ciclu. Respingem.
• Costul 4, muchia (3,4): 4 era izolat. Acceptăm. Avem 3 muchii = n-1, deci ne oprim.
• Costul 5, muchia (2,4): nici n-o mai privim — arborele e complet.

Muchiile alese sunt (1,2), (2,3), (3,4), cu cost total 1 + 2 + 4 = 7.

Implementare C++

Sortăm muchiile crescător și adăugăm fiecare muchie dacă nu unește două noduri deja conectate. „Sunt conectate?" îl aflăm cu un union-find rudimentar: fiecare nod are un reprezentant; două noduri sunt în aceeași componentă dacă au același reprezentant.

#include <iostream>
#include <algorithm>
using namespace std;

struct Muchie {
    int x, y, cost;
};

int rep[105];   // reprezentantul componentei fiecarui nod

// gaseste reprezentantul componentei nodului u
int gaseste(int u) {
    while (rep[u] != u)
        u = rep[u];
    return u;
}

int main() {
    int n = 4;
    Muchie m[] = {{1, 2, 1}, {2, 3, 2}, {1, 3, 3}, {3, 4, 4}, {2, 4, 5}};
    int nrMuchii = 5;

    // sortare crescatoare dupa cost
    sort(m, m + nrMuchii, [](Muchie a, Muchie b) {
        return a.cost < b.cost;
    });

    for (int i = 1; i <= n; i++)
        rep[i] = i;     // initial fiecare nod e singur in componenta sa

    long long costTotal = 0;    // suma poate depasi int la grafuri mari
    int alese = 0;
    for (int i = 0; i < nrMuchii && alese < n - 1; i++) {
        int rx = gaseste(m[i].x);
        int ry = gaseste(m[i].y);
        if (rx != ry) {         // capete in componente diferite => nu face ciclu
            rep[rx] = ry;       // unim cele doua componente
            costTotal += m[i].cost;
            alese++;
        }
    }

    cout << costTotal;          // 7
    return 0;
}

Versiunea de mai sus e cea mai simplă posibilă pentru a vedea mecanismul. La clasa despre Kruskal vei accelera gaseste cu compresia drumului, dar ideea rămâne identică: sortezi, apoi accepți muchia doar dacă unește componente diferite.

Complexitate

Pentru un graf cu n noduri și m muchii, costul e dominat de sortarea muchiilor.

Sortarea costă O(m log m); parcurgerea muchiilor mai adaugă O(m) verificări de componentă, deci termenul de sortare domină.