- Curent
- În arbore
- Lângă arbore
- Cea mai bună muchie până acum
Algoritmul lui Prim
Algoritmul lui Prim construiește un arbore parțial de cost minim, cel mai ieftin set de muchii care leagă toate nodurile, crescând un singur arbore de la un start. La fiecare pas adaugă nodul care poate fi atins din arbore prin cea mai scurtă muchie. Faceți clic pe un nod ca să porniți de acolo și avansați pas cu pas ca să vedeți nodurile în așteptare, cele mai bune muchii ale lor și cum crește arborele. Apăsați Redare pentru a urmări cum crește arborele sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Faceți clic pe un nod ca să devină start: arborele crește de acolo. Numărul de pe fiecare muchie este lungimea ei. Sub graf sunt nodurile care așteaptă să se alăture, fiecare cu lungimea celei mai bune muchii a sa spre arbore, trasată cu linie întreruptă. Graf nou creează alt graf; alegeți câte noduri și muchii are. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Faceți clic pe un nod ca să devină start: arborele crește de acolo.
- Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde.
- Urmăriți nodurile în așteptare de sub graf, fiecare cu cea mai bună muchie a sa spre arbore. Graf nou creează alt graf de încercat.
Cum funcționează algoritmul lui Prim
Începeți cu un arbore format dintr-un singur nod. Fiecare nod din afara arborelui își amintește cea mai scurtă muchie a sa spre arbore, dacă are una. Luați de fiecare dată nodul cu cea mai scurtă muchie, adăugați-l împreună cu acea muchie la arbore și verificați-i muchiile: dacă una este mai scurtă decât cea mai bună muchie de până acum a unui vecin, devine noua cea mai bună muchie a vecinului. Când toate nodurile s-au alăturat, arborele are cu o muchie mai puțin decât numărul de noduri, iar lungimea lui totală este cea mai mică posibilă.
Prim și Dijkstra
Algoritmul lui Prim și algoritmul lui Dijkstra arată aproape la fel: amândoi cresc o regiune de la un start și țin nodurile în așteptare într-o coadă de priorități. Diferența este numărul din coadă. Dijkstra păstrează întreaga distanță a fiecărui nod de la start; Prim doar lungimea singurei sale celei mai bune muchii spre arbore. Așadar Dijkstra construiește un arbore de drumuri minime, iar Prim un arbore cu cea mai mică lungime totală, și cei doi arbori diferă adesea.
Întrebări frecvente
Ce este algoritmul lui Prim?
Un algoritm greedy care construiește un arbore parțial de cost minim al unui graf ponderat crescând un singur arbore dintr-un nod de start și adăugând mereu cea mai scurtă muchie care leagă arborele de un nod din afara lui.
Contează nodul de start?
Doar pentru ordine: din orice start, algoritmul lui Prim ajunge la un arbore parțial cu aceeași lungime totală minimă. Când unele muchii au lungimi egale, arborele însuși poate fi diferit.
Cine a inventat algoritmul lui Prim?
Vojtěch Jarník l-a descris primul, în 1930. Robert Prim l-a redescoperit în 1957, iar Edsger Dijkstra în 1959, așa că i se mai spune algoritmul lui Jarník sau algoritmul Prim–Jarník.
Cât de rapid este algoritmul lui Prim?
Cu un heap binar, efortul crește cu E log V pentru V noduri și E muchii. Cu un simplu tablou în loc de heap, are nevoie de aproximativ V² pași, ceea ce e mai bine pentru grafurile dense, în care aproape orice pereche de noduri este legată.
Este graful meu trimis undeva?
Nu. Graful este creat și arborele este construit în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor