Algoritmul lui Prim
Imaginați-vă că trageți cablu de la o centrală electrică: legați întâi cel mai apropiat oraș, apoi orașul cel mai apropiat de oricare loc deja legat și așa mai departe. Acesta este algoritmul lui Prim și ajunge mereu la cea mai ieftină rețea posibilă.
Ideea
Un arbore parțial de cost minim leagă toate nodurile unui graf ponderat cu cea mai mică lungime totală posibilă a muchiilor. Algoritmul lui Prim îl construiește crescând un singur arbore în afară, de la un start. Arborele nu se rupe niciodată în bucăți: la fiecare pas i se alătură exact un nod nou, prin cea mai scurtă muchie care iese din arbore.
Pas cu pas
Puneți startul în arbore. Pentru fiecare nod din afara arborelui, păstrați cea mai bună muchie a lui: cea mai scurtă muchie spre un nod din arbore. Apoi repetați: alegeți nodul din afară a cărui cea mai bună muchie este cea mai scurtă, adăugați-l la arbore cu acea muchie și verificați-i muchiile. Un vecin din afara arborelui care acum poate fi atins printr-o muchie mai scurtă primește acea muchie drept noua sa cea mai bună. Opriți-vă când toate nodurile sunt în arbore.
Un exemplu
Luați muchiile A–B de lungime 1, B–C 2, A–C 3, C–D 4 și B–D 5 și porniți din A. Muchiile lui A îi dau lui B cea mai bună muchie 1, iar lui C cea mai bună muchie 3. B este cel mai aproape, deci se alătură prin A–B; muchiile lui îl îmbunătățesc pe C la 2 și îi dau lui D 5. C se alătură prin B–C, iar muchia lui C–D îl îmbunătățește pe D la 4. În final, D se alătură prin C–D. Arborele A–B, B–C, C–D are lungimea totală 1 + 2 + 4 = 7.
De ce este corect
La fiecare pas nodurile sunt împărțite în două grupuri: cele din arbore și cele din afară. Proprietatea tăieturii spune că cea mai scurtă muchie dintre două astfel de grupuri face mereu parte dintr-un arbore parțial de cost minim. Prim adaugă mereu exact acea muchie, deci arborele construit până acum poate fi întotdeauna completat până la un arbore parțial de cost minim, iar când toate nodurile s-au alăturat, chiar este unul.
Istorie și viteză
Matematicianul ceh Vojtěch Jarník a publicat algoritmul în 1930. Robert Prim l-a redescoperit la Bell Labs în 1957, iar Edsger Dijkstra încă o dată în 1959. Cu nodurile în așteptare într-un heap binar, efortul crește cu E log V pentru V noduri și E muchii; cu un tablou simplu este aproximativ V², ceea ce e mai bine când aproape orice pereche de noduri este legată. Cu un heap Fibonacci este E + V log V.
Explorați
Deschideți aplicația, faceți clic pe un nod ca să porniți de acolo și apăsați Pas. Nodurile din arbore sunt verzi, cele în așteptare albastre, iar cea mai bună muchie a fiecărui nod în așteptare este trasată cu linie întreruptă. Nodurile în așteptare sunt listate sub graf cu lungimea celei mai bune muchii a lor, de la cea mai scurtă: primul se alătură următorul. Porniți din noduri diferite și vedeți cum se schimbă ordinea, în timp ce totalul rămâne același.
Întrebări frecvente
Care este diferența dintre algoritmul lui Prim și cel al lui Dijkstra?
Amândoi cresc o regiune de la un start folosind o coadă de priorități. Prim ordonează un nod în așteptare după lungimea singurei sale celei mai bune muchii spre arbore; Dijkstra după întreaga lui distanță de la start. Prim dă un arbore parțial de cost minim, Dijkstra un arbore de drumuri minime.
Funcționează algoritmul lui Prim cu lungimi negative ale muchiilor?
Da. Spre deosebire de algoritmul lui Dijkstra, Prim doar compară muchiile între ele, deci lungimile negative nu creează probleme: găsește tot un arbore parțial cu cea mai mică sumă.
Ce se întâmplă dacă graful nu este conex?
Atunci algoritmul lui Prim se oprește după ce a atins toate nodurile la care poate ajunge: dă un arbore parțial de cost minim doar pentru partea care conține startul. Dacă îl rulați din nou dintr-un nod încă neatins, obțineți o pădure parțială de cost minim.
Care este mai bun, algoritmul lui Prim sau cel al lui Kruskal?
Niciunul nu câștigă mereu. Prim se potrivește grafurilor dense și celor memorate ca liste de vecini; Kruskal grafurilor rare date ca listă de muchii. Amândoi găsesc un arbore cu aceeași lungime totală.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați algoritmul lui Prim