Algoritmii Kruskal și Prim

Kruskal și Prim caută un arbore parțial de cost minim într-un graf neorientat conex ponderat. Kruskal examinează muchiile în ordine crescătoare a costului și le ia dacă nu formează ciclu. Prim pornește de la un vârf și adaugă cea mai ieftină muchie care leagă arborele construit de un vârf din afară.

Algoritmii Kruskal și Prim determină un arbore parțial de cost minim al unui graf neorientat conex ponderat, adică $n-1$ muchii care unesc toate vârfurile cu suma costurilor cea mai mică. Ambii sunt greedy: la fiecare pas aleg muchia cea mai ieftină permisă. Kruskal sortează muchiile crescător după cost și le adaugă pe rând, dacă nu formează ciclu cu cele alese; verificarea se face rapid cu o structură de mulțimi disjuncte, în care două vârfuri sunt în aceeași componentă dacă au aceeași rădăcină. Prim pornește dintr-un vârf și, la fiecare pas, adaugă cea mai ieftină muchie care leagă arborele construit de un vârf din afara lui. Pentru un graf deconectat nu există arbore parțial care să cuprindă toate vârfurile. Dacă există ponderi egale, pot exista arbori minimi diferiți, dar toți au același cost minim.

Graful are patru vârfuri și muchiile [1,2]:1, [2,3]:2, [3,4]:3, [1,3]:4, [1,4]:8.

Exemplul 1 — Kruskal. Muchiile sunt deja în ordinea crescătoare a costurilor:

#include <iostream>
using namespace std;
int t[5];
int rad(int x) { return t[x] == x ? x : t[x] = rad(t[x]); }
int main() {
    int e[5][3] = {{1, 2, 1}, {2, 3, 2}, {3, 4, 3}, {1, 3, 4}, {1, 4, 8}};
    int cost = 0;
    for (int i = 1; i <= 4; ++i) t[i] = i;
    for (auto& m : e) {
        int a = rad(m[0]), b = rad(m[1]);
        if (a == b) {
            cout << "respins " << m[0] << "-" << m[1] << "\n";
            continue;
        }
        t[a] = b;
        cost += m[2];
        cout << m[0] << "-" << m[1] << "\n";
    }
    cout << cost;
}

Se afișează 1-2, 2-3, 3-4, apoi respins 1-3 și respins 1-4, iar costul este 6. Primele trei muchii leagă toate vârfurile și însumează $1+2+3=6$. Muchia [1,3] este respinsă, deoarece ar închide ciclul 1–2–3–1, iar [1,4] este respinsă, deoarece 1 și 4 sunt deja în aceeași componentă. Sortarea muchiilor dă pentru Kruskal $O(m\log m)$ timp.

Exemplul 2 — Prim cu matrice. Se menține pentru fiecare vârf din afara arborelui costul d[v] al celei mai ieftine muchii către arbore și vârful tata[v] de care se leagă. Se alege vârful cu d minim, se adaugă la arbore și se actualizează vecinii lui:

#include <iostream>
using namespace std;
int main() {
    const int INF = 1000000, n = 4;
    int c[5][5], d[5], tata[5] = {}, in[5] = {}, cost = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) c[i][j] = INF;
    c[1][2] = c[2][1] = 1; c[2][3] = c[3][2] = 2; c[3][4] = c[4][3] = 3;
    c[1][3] = c[3][1] = 4; c[1][4] = c[4][1] = 8;
    for (int i = 1; i <= n; ++i) d[i] = INF;
    d[1] = 0;
    for (int pas = 1; pas <= n; ++pas) {
        int u = 0;
        for (int i = 1; i <= n; ++i)
            if (!in[i] && (u == 0 || d[i] < d[u])) u = i;
        in[u] = 1;
        cost += d[u];
        if (tata[u]) cout << tata[u] << "-" << u << " ";
        for (int v = 1; v <= n; ++v)
            if (!in[v] && c[u][v] < d[v]) { d[v] = c[u][v]; tata[v] = u; }
    }
    cout << "\n" << cost;
}

Se afișează 1-2 2-3 3-4, apoi 6. Din vârful 1 frontiera are muchiile [1,2]:1, [1,3]:4 și [1,4]:8, deci se alege [1,2]. Din $\{1,2\}$ cea mai ieftină muchie către exterior este [2,3]:2; din $\{1,2,3\}$ este [3,4]:3. Arborele rezultat are costul 6, ca la Kruskal. Cu matrice, Prim folosește $O(n^2)$ timp.

Exemplul 3 — în formatul examenului. Un graf cu 5 vârfuri are muchiile [1,2]:3, [1,3]:5, [2,3]:1, [2,4]:4, [3,4]:2, [3,5]:6 și [4,5]:7. Care este costul unui arbore parțial de cost minim?

• a) 10
• b) 12
• c) 13
• d) 15

Răspunsul corect este b). Kruskal ia [2,3]:1 și [3,4]:2, apoi [1,2]:3. Muchia [2,4]:4 este respinsă, fiindcă 2 și 4 sunt deja unite prin 3, iar [1,3]:5 este respinsă, fiindcă 1 și 3 sunt deja unite prin 2. Muchia [3,5]:6 leagă vârful 5. Costul este $1+2+3+6=12$, cu 4 muchii. Varianta a) adună $1+2+3+4$ și acceptă [2,4], care închide ciclul 2–3–4. Varianta c) leagă vârful 5 prin [4,5]:7, mai scump decât [3,5]:6. Varianta d) adună primele cinci costuri, $1+2+3+4+5$, fără să verifice ciclurile.

Exemplul 4 — ponderi egale. Graful are vârfurile 1, 2, 3 și muchiile [1,2]:1, [2,3]:1, [1,3]:1. Kruskal ia primele două muchii din ordinea sortării, iar a treia este respinsă, deoarece 1 și 3 sunt deja în aceeași componentă. Orice pereche de două muchii formează un arbore parțial, deci există trei arbori minimi diferiți, toți cu costul $1+1=2$.

Greșeli frecvente

• Greșit: Kruskal acceptă orice muchie ieftină chiar dacă produce ciclu.
  Corect: respinge muchiile care închid un ciclu.
• Greșit: Prim poate alege o muchie între două vârfuri încă neincluse.
  Corect: muchia aleasă trebuie să traverseze frontiera arborelui curent.
• Greșit: două implementări trebuie să dea exact aceleași muchii la ponderi egale.
  Corect: pot exista arbori minimi diferiți.

Înainte și după