Algoritmul lui Prim

De la Wikipedia, enciclopedia liberă

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.

Cuprins 1 Descriere 2 Exemplu 3 Pseudocod 3.1 Min-heap 4 Legături externe

[modifică] 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

[modifică] 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	A, D
	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	A, D, 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	A, D, 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	A, D, 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	A, D, 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	A, D, F, B, E, C, G

[modifică] Pseudocod

[modifică] 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

[modifică] Legături externe

• Arbore parţial de cost minim: Algoritmul lui Prim
• Algoritmul lui Prim (Java Applet)
• Implementări C++, Java şi C# ale algoritmului lui Prim