Algoritmul lui Prim

Considerăm un graf neorientat ponderat (cu costuri) conex G. Se numește arbore parțial un graf parțial al lui G care este arbore. Se numește arbore parțial de cost minim un arbore parțial pentru care suma costurilor muchiilor este minimă.

Dacă graful nu este conex, vorbim despre o pădure parțială de cost minim.

Algoritmul lui Prim permite determinarea unui arbore parțial de cost minim (APM) într-un graf ponderat cu N noduri.

Descrierea algoritmului

Determinarea APM-ului se face astfel:

• se stabilește un nod de plecare; acesta va fi rădăcina arborelui, care se va crea pas cu pas, prin adăugarea de noi noduri;
• în mod repetat:
  • se alege un nod neadăugat încă în arborele curent pentru care muchia dintre el și un nod din arbore are cost minim;
  • se adăugă nodul în arbore;
• când nu se mai poate face alegerea unui asemenea nod, fie au fost adăugate toate nodurile, fie graful nu este conex și au fost adăugate în arbore toate nodurile din componenta conexă a nodul inițial;
• dacă graful nu este conex, continuăm cu următoarea componentă conexă.

Observație: arborele parțial de cost minim al unui graf neorientat nu este unic, însă toate APM-urile vor avea același cost.

Exemplu

Mai jos este descris modul în care se aleg nodurile care se adaugă în arbore pentru un graf ponderat cu N=9 noduri:

Algoritmul poate fi implementat în mai multe moduri, cu complexități diferite.

Varianta \(N^3\)

• în mod repetat (de cel mult N-1 ori):
  • se aleg două noduri adiacente, un nod din arbore și un nod din afara acestuia, astfel încât muchia determinată de cele două noduri să aibă costul minim
  • nodul ales din afara arborelui curent se va adăuga în arbore

Varianta \(N^2\)

Față de varianta anterioară se evită căutarea propriu zisă a nodului din arbore, căutându-se efectiv numai nodul din afara acestuia. Pentru aceasta se păstrează un șir d[] cu următoarea semnificație: pentru un nod k încă neadăugat în arbore, d[k] reprezintă costul minim al unei muchii având o extremitate k și o extremitate în arbore; dacă o asemenea muchie nu există d[k] = INFINIT.

Dacă determinarea succesivă a nodurilor din afara arborelui se face prin parcurgerea șirului d[], complexitatea devine O(N2).

Varianta \(N \log N\)

Se poate evita parcurgerea șirului d[] prin memorarea nodurilor din arbore într-o structură de date de tip heap, în vârful heap-ului fiind nodul k pentru care d[k] are valoare minimă. În acest fel complexitatea algoritmului devine O(N logN).

Vezi și

• Algoritmul lui Kruskal