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: 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
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ă]