Algoritmul lui Prim


Editat de Candale Silviu (silviu) la data 2019-03-10

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:

Nodul ințial este 1. Costul curent al APM este 0
Se adaugă nodul 2. Muchia folosită este (1,2). Costul curent al APM este 40
Se adaugă nodul 3. Muchia folosită este (2,3). Costul curent al APM este 120
Se adaugă nodul 9. Muchia folosită este (3,9). Costul curent al APM este 140
Se adaugă nodul 6. Muchia folosită este (3,6). Costul curent al APM este 180
Se adaugă nodul 7. Muchia folosită este (6,7). Costul curent al APM este 200
Se adaugă nodul 8. Muchia folosită este (7,8). Costul curent al APM este 210
Se adaugă nodul 4. Muchia folosită este (3,4). Costul curent al APM este 280
Se adaugă nodul 5. Muchia folosită este (4,5). Costul curent al APM este 370

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

Varianta N3

  • î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 N2

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 logN

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).

Fișiere atașate


Probleme ataşate

Nr. Problema Clasa Dificultate Operații I/O
1 #0590 - Prim 11 ușoară fișiere