Algoritmul lui Prim

Algoritmul lui Prim este un algoritm din teoria grafurilor care găsește arborele parțial de cost minim al unui graf conex ponderat. Înseamnă că găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și al cărui cost este minimizat. Algoritmul a fost descoperit în 1930 de către matematicianul Vojtěch Jarník și apoi, independent, de informaticienii Robert C. Prim în 1957 și redescoperit de Edsger Dijkstra în 1959. De aceea mai este numit Algoritmul DJP, algoritmul Jarník sau algoritmul Prim-Jarník.

Descriere

Algoritmul incrementează mărimea unui arbore, pornind de la un nod, până când sunt incluse toate nodurile.

• Intrare: Un graf conex ponderat cu nodurile V și muchiile E.
• Initializare: V_nou = {x}, unde x este un nod arbitrar (punct de plecare) din V, E_nou= {}
• repetă până când V_nou=V:
  • Alege muchia (u,v) din E de cost minim astfel încât u este în V_nou și v nu e (dacă există mai multe astfel de muchii, se alege arbitrar)
  • Se adaugă v la V_nou, (u,v) la E_nou
• Ieșire: V_nou și E_nou descriu arborele parțial de cost minim

Exemplu

Imagine	Descriere	Nevizitate	Vecini	Mulțimea soluție
	Acesta este graful ponderat original. Nu este un arbore pentru că din definiția arborelui se cere să nu existe cicluri. Numerele de pe muchii reprezintă costul. Nici un arc nu e evidențiat, iar nodul D a fost ales arbitrar ca punct de plecare.	C, G	A, B, E, F	D
	Al doilea nod ales este unul din vecinii lui D: A se află la distanța 5, B la 9, E la 15 și F la 6. Dintre acestea, 5 este cel mai mic cost, deci se evidențiază nodul A și muchia DA.	C, G	B, E, F	D,A
	Următorul nod ales este unul din vecinii lui D sau A. B se află la distanța 9 de D și la 7 de A, E la 15 și F la 6. 6 este cel mai mic, deci se evidențiază nodul F și muchia DF.	C	B, E, G	D, A, F
	Nodul B, care e la distanța 7 de A, este evidențiat. Aici, muchia DB este evidențiată cu roșu, deoarece ambele noduri B și D au fost deja evidențiate, deci nu poate fi folosită.	null	C, E, G	D, A, F, B
	În acest caz, putem alege între C, E și G. C este la 8 față de B, E este la 7 de B și G la 11 față de F. E se află cel mai aproape, deci se evidențiază nodul E și muchia EB. Alte două muchii au fost marcate cu roșu, deoarece nodurile lor au fost deja vizitate.	null	C, G	D, A, F, B, E
	Aici sunt disponibile doar nodurile C și G. C se află la distanța 5 de E, iar G la 9 de E. C este ales, deci este evidențiat împreună cu muchia EC. Muchia BC este marcată cu roșu.	null	G	D, A, F, B, E, C
	Nodul G este singurul rămas. Se află la distanța 11 față de F și la 9 față de E. E este mai aproape, deci se evidențiază muchia EG. Au fost incluse toate vârfurile, deci arborele parțial de cost minim este evidențiat cu verde. În acest caz, are costul 39.	null	null	D, A, F, B, E, C, G

Pseudocod

Min-heap

Inițializare

intrare: Un graf, o funcție care returnează costul muchiilor și un nod inițial r

plasează toate nodurile în mulțimea celor nevizitate, adaugă nodul inițial la arbore și plasează toate nodurile într-un min-heap.

for fiecare v in graf
      distanțăMin [v] ← ∞
      părinte [v] ← -1
      listaDeAdiac [v] ← mulțimeaVidă
      înQ [v] ← true
distanță [r] ← 0
Q ← V

Algoritm

În descrierea algoritmului de mai sus,

nodProxim este Q[0], acum ultim

vecini este v din Q unde distanța față de v < ∞, după ce vârful proxim este eliminat

nevizitat este v din Q unde distanța față de v = ∞, după ce vârful proxim este eliminat

Bucla while se va termina când nu mai există noduri care pot fi returnate.

complexitate în timp: V pentru buclă, log(V) pentru eliminare

while ultim ← eliminăMin(Q)
    înQ [ultim] ← false
    adaugă ultim la listaDeAdiac [părinte [ultim]]
    adaugă părinte [ultim] la listaDeAdiac [ultim]

complexitate în timp: E/V, numărul mediu de noduri

    for each adiacent al lui ultim
    if (înQ [adiacent]) și (cost(ultim, adiacent) < distanțăMin [adiacent])
        părinte [adiacent] ← ultim
        distanțăMin [adiacent] ← cost(ultim, adiacent)

complexitate în timp: log(V), înățimea heap-ului

        update adiacent în Q, ordonează după distanțăMin

Legături externe

• Arbore parțial de cost minim: Algoritmul lui Prim^{[nefuncțională]}