Algoritmul lui Kruskal

Sortați muchiile, luați-o pe cea mai scurtă, nu închideți niciodată o buclă. Algoritmul lui Kruskal este poate cel mai simplu algoritm greedy care există și totuși găsește mereu cel mai ieftin mod de a lega toate nodurile unui graf.

Un graf în care cresc deodată mai multe părți ale unui arbore, o muchie sărită care ar închide un ciclu trasată cu linie întreruptă roșie și dedesubt lista muchiilor rămase de încercat
Un graf în care cresc deodată mai multe părți ale unui arbore, o muchie sărită care ar închide un ciclu trasată cu linie întreruptă roșie și dedesubt lista muchiilor rămase de încercat

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 Kruskal nu crește un singur arbore de la un start. Privește tot graful deodată, începe cu fiecare nod ca parte separată și tot unește părți prin cea mai scurtă muchie disponibilă, până când rămâne o singură parte.

Pas cu pas

Sortați muchiile de la cea mai scurtă la cea mai lungă. Încercați-le în această ordine. Dacă cele două capete ale unei muchii sunt în părți diferite, adăugați-o la arbore: cele două părți devin una. Dacă ambele capete sunt deja în aceeași parte, muchia ar închide un ciclu, deci săriți peste ea. Cu n noduri, arborele este gata după n − 1 muchii, iar muchiile rămase nu mai trebuie verificate deloc.

Un exemplu

Luați muchiile A–B de lungime 1, B–C 2, A–C 3, C–D 4 și B–D 5. Kruskal adaugă A–B, apoi B–C, care îl leagă pe C de partea A–B. Urmează A–C, dar A și C sunt deja într-o singură parte, deci ar închide ciclul A–B–C și este sărită. C–D îl aduce pe D, iar acum toate cele patru noduri formează un singur arbore cu trei muchii, cu lungimea totală 7. B–D, cea mai lungă muchie, nici nu mai este încercată.

Union-find

Singura întrebare grea pe care o pune algoritmul lui Kruskal este: sunt aceste două noduri deja în aceeași parte? O structură union-find răspunde la ea. Fiecare parte este un mic arbore de legături care indică spre un reprezentant. Find urmează legăturile până la reprezentant; union agață un reprezentant sub celălalt. Comprimarea drumului, care face ca fiecare nod vizitat să indice direct spre reprezentant, și uniunea după mărime țin legăturile atât de scurte încât fiecare întrebare durează un timp aproape constant.

Istorie și viteză

Joseph Kruskal a publicat algoritmul în 1956, într-un articol scurt din Proceedings of the American Mathematical Society. Sortarea muchiilor este partea cea mai lentă, deci efortul crește cu E log E pentru E muchii. Dacă muchiile sunt deja sortate sau lungimile lor sunt numere întregi mici, este aproape liniar.

Explorați

Deschideți aplicația și apăsați Pas. Muchiile rămase de încercat sunt listate sub graf, de la cea mai scurtă. Fiecare muchie care unește două părți devine verde; fiecare muchie care ar închide un ciclu este trasată cu linie întreruptă roșie. Urmăriți cum mai multe părți mici cresc în diferite zone ale grafului și se unesc, și observați că ultimele muchii adesea nu mai sunt încercate.

Întrebări frecvente

De ce sortează algoritmul lui Kruskal muchiile?

Ca fiecare muchie pe care o adaugă să fie cea mai scurtă care încă unește două părți. Această alegere greedy este mereu sigură datorită proprietății tăieturii, iar fiecare muchie sărită este cea mai lungă de pe ciclul pe care l-ar închide, deci nu este niciodată necesară.

Ce este o structură de mulțimi disjuncte?

Un alt nume pentru union-find: o structură care ține o colecție de mulțimi separate, aici părțile pădurii în creștere, și poate spune repede cărei mulțimi îi aparține un element și poate uni două mulțimi.

Funcționează algoritmul lui Kruskal pe un graf neconex?

Da. Pur și simplu se termină cu câte un arbore pentru fiecare parte conexă a grafului, o pădure parțială de cost minim, pentru că nicio muchie nu poate uni părți care nu sunt legate.

Se folosește algoritmul lui Kruskal și la altceva?

Oprit mai devreme, înainte ca ultimele părți să se unească, grupează nodurile în clustere: aceasta este gruparea single-linkage. Rulat pe o grilă cu lungimi aleatorii ale muchiilor, generează un labirint.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Încercați algoritmul lui Kruskal