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.

Descriere[modificare | modificare sursă]

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: Vnou = {x}, unde x este un nod arbitrar (punct de plecare) din V, Enou= {}
  • repetă până când Vnou=V:
    • Alege muchia (u,v) din E de cost minim astfel încât u este în Vnou și v nu e (dacă există mai multe astfel de muchii, se alege arbitrar)
    • Se adaugă v la Vnou, (u,v) la Enou
  • Ieșire: Vnou și Enou descriu arborele parțial de cost minim

Exemplu[modificare | modificare sursă]

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[modificare | modificare sursă]

Min-heap[modificare | modificare sursă]

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
QV

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[modificare | modificare sursă]

Commons
Commons
Wikimedia Commons conține materiale multimedia legate de Algoritmul lui Prim