- Curent
- În arbore
- Lângă arbore
- Cea mai bună muchie până acum
- Ar închide un ciclu
Arbore parțial de cost minim
Vreți să legați fiecare oraș prin cablu, fiecare casă prin conducte de apă sau fiecare calculator dintr-o rețea, folosind cât mai puțin material. Răspunsul este un arbore parțial de cost minim: mulțimea de muchii care leagă toate nodurile cu cea mai mică lungime totală. Alegeți algoritmul lui Kruskal sau Prim și avansați pas cu pas ca să vedeți cum crește arborele, câte o muchie permisă, cea mai scurtă. 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. Alegeți algoritmul: Kruskal încearcă muchiile de la cea mai scurtă la cea mai lungă, Prim crește un singur arbore de la start; faceți clic pe un nod ca să devină startul pentru Prim. Numărul de pe fiecare muchie este lungimea ei. Sub graf este lista muchiilor rămase de încercat sau a nodurilor care așteaptă să se alăture, cu lungimea celei mai bune muchii a lor spre arbore. 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ă
- Alegeți algoritmul lui Kruskal sau Prim. Pentru Prim, faceți clic pe un nod ca să devină start.
- 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 cum muchiile intră în arbore și cum crește lungimea totală. Graf nou creează alt graf de încercat.
Algoritmul lui Kruskal
Sortați toate muchiile de la cea mai scurtă la cea mai lungă și încercați-le în această ordine. Dacă o muchie unește două părți care nu sunt încă legate, intră în arbore. Dacă cele două capete ale ei sunt deja legate prin arbore, ar închide un ciclu, deci este sărită. Opriți-vă când arborele are cu o muchie mai puțin decât numărul de noduri. Ca să afle repede dacă două noduri sunt deja legate, algoritmul lui Kruskal ține părțile într-o structură union-find.
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. Adăugați de fiecare dată nodul a cărui muchie este cea mai scurtă, împreună cu acea muchie, și verificați-i muchiile: una dintre ele poate oferi unui vecin o cale mai scurtă spre arbore. Algoritmul lui Prim seamănă cu algoritmul lui Dijkstra, dar compară muchii individuale, nu distanțe întregi de la start. Ambii algoritmi ajung mereu la aceeași lungime totală.
Întrebări frecvente
Ce este un arbore parțial de cost minim?
Pentru un graf conex ale cărui muchii au lungimi, un arbore parțial este o mulțime de muchii care leagă toate nodurile fără niciun ciclu; cu n noduri are mereu n − 1 muchii. Un arbore parțial de cost minim este un arbore parțial cu cea mai mică lungime totală posibilă.
Care este diferența dintre algoritmul lui Kruskal și cel al lui Prim?
Algoritmul lui Kruskal parcurge muchiile întregului graf de la cea mai scurtă la cea mai lungă și unește părți separate într-un singur arbore. Algoritmul lui Prim crește un singur arbore de la un start, adăugând mereu cea mai scurtă muchie care iese din el. Amândoi sunt greedy și găsesc un arbore cu aceeași lungime totală; Kruskal se potrivește grafurilor rare, Prim celor dense.
Este arborele parțial de cost minim unic?
Da, când toate lungimile muchiilor sunt diferite. Când unele lungimi sunt egale, pot exista mai mulți arbori cu același total minim, iar algoritmii pot alege arbori diferiți, în funcție de cum aleg între muchiile egale.
Este un arbore parțial de cost minim același lucru cu drumurile cele mai scurte?
Nu. Arborele parțial de cost minim păstrează mică lungimea totală a tuturor muchiilor, dar drumul dintre două noduri în arbore poate fi mult mai lung decât cel mai scurt drum dintre ele. Pentru drumuri cele mai scurte, folosiți algoritmul lui Dijkstra.
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