Modul 08 — Prim: acoperirea de cost minim

Ce căutăm: arborele parțial de cost minim

Dintre toate „schemele de cablare" care leagă cele 6 noduri, o alegem pe cea mai ieftină.

De ce „arbore parțial"?

Parțial — păstrăm toate nodurile, alegem doar o parte din muchii (graful parțial, M04!). Arbore — conex și FĂRĂ cicluri: un ciclu ar însemna un cablu în plus degeaba. Un arbore cu n noduri are mereu exact n−1 muchii — la noi: 5 cabluri pentru 6 stâlpi.

Ideea lui Prim

Pornești dintr-un nod și crești rețeaua ca un cristal: la fiecare pas adaugi cea mai ieftină muchie care leagă un nod DIN rețea de unul DIN AFARA ei. Lăcomie pură (X·M12) — și, ca la Dijkstra, cu certificat de corectitudine.

Prim pas cu pas — iluminatul stradal

Același graf ca la Dijkstra (M07) — dinadins! Verde = în rețea, auriu punctat = muchiile-candidat de la granița rețelei, albastru = încă nelegat.

pornim rețeaua din nodul 1 — apasă Pas 👆

Tabelul de sub graf ține „prețul de conectare": pentru fiecare nod din afară, costul celei mai ieftine muchii spre rețea — NU distanța de la start! Când un nod intră în rețea, prețul lui se fixează, iar vecinii lui își pot IEFTINI conectarea.

Prim vs Dijkstra — capcana BAC-ului

Aceeași schelă (fixează minimul, actualizează vecinii), un singur rând de cod diferit — și rezultate complet diferite.

	Dijkstra (M07)	Prim (M08)
obiectiv	drum minim de la sursă spre FIECARE nod	rețea totală minimă care leagă TOATE nodurile
actualizarea	d[v] = min(d[v], d[u] + c[u][v]) — cost CUMULAT	d[v] = min(d[v], c[u][v]) — DOAR muchia!
rezultat	vector de distanțe + arborele drumurilor	arborele parțial de cost minim
pe graful nostru	drumul 1→6 costă 12	toată rețeaua costă 13

Dovada că-s diferite: arborele drumurilor lui Dijkstra (cu muchia 3–5, cost 8) însumează 19; arborele lui Prim (cu 4–5 în locul ei) doar 13. Drumurile minime NU formează rețeaua minimă! La BAC, verifică formula de actualizare: cu d[u] + … e Dijkstra, fără — e Prim.

Implementarea de școală — O(n²)

1for (int i = 1; i <= n; i++) { d[i] = c[1][i]; tata[i] = 1; }

2viz[1] = 1; int total = 0;

3for (int pas = 1; pas < n; pas++) {

4 int u = nodul nevizitat cu d[u] minim; // cea mai ieftină conectare

5 viz[u] = 1; total += d[u]; // muchia (tata[u], u) intră în APM

6 for (int v = 1; v <= n; v++)

7 if (!viz[v] && c[u][v] < d[v]) // FĂRĂ d[u] + !

8 { d[v] = c[u][v]; tata[v] = u; }

Fișa de sinteză

Prim, condensat. Cu asta, Faza 2 — grafurile — e completă!

APM = graf parțial conex fără cicluri, cu suma costurilor minimă; are exact n−1 muchii.

Prim: crește rețeaua dintr-un nod, adăugând mereu cea mai ieftină muchie spre exterior.

Actualizarea: d[v] = min(d[v], c[u][v]) — doar costul muchiei, FĂRĂ cumul. Diferența față de Dijkstra!

tata[v] = capătul din rețea al celei mai ieftine conectări → muchiile APM sunt (tata[u], u).

Greedy cu certificat: cea mai ieftină muchie peste „graniță" e mereu sigură într-un APM.

Drumuri minime ≠ rețea minimă: pe graful lecției, 19 vs 13 — cele două arbori diferă!

Faza 2 încheiată! Ai toată teoria grafurilor de liceu. Urmează Faza 3: graful conex fără cicluri pe care tocmai l-a construit Prim are un nume — ARBORELE. Îl studiem ca model de sine stătător.

Toată rețeaua, cablu minim