Joseph Bernard Kruskal Jr. je bil ameriški matematik, statistik, računalniški znanstvenik in psihometrik. Kot računalniški znanstvenik je najbolj znan po algoritmu za računanje minimalnega vpetega drevesa na uteženem grafu, ki ga ja objavil leta 1956 v matematični reviji Proceedings of the American Mathematical Society.
Prva stran članka.
Za reševanje tega problema poznamo še Primov algoritem, Dijkstrov algoritem, Borůvkajev algoritem.

Vpeto drevo T grafa G=(V,E) je drevo, sestavljeno iz vseh točk množice točk V in minimalnim številom povezav iz množice E. Na vpetem drevesu ni ciklov.
Pri strategiji minimalnega vpetega drevesa na povezanem grafu, kjer ima vsaka povezava svojo ceno oz. težo, iščemo najcenejše vpeto drevo oz. vpeto drevo, katerega vsota cen povezav je najmanjša. Problema se lotimo s požrešno metodo: v vsakem koraku izberemo najcenejšo povezavo in pazimo, da de ustvarimo kakšnega cikla.

Strategija je sledeča:

• ustvarimo gozd dreves F, kjer je vsako vozlišče drevo zase,
• ustvarimo nabor povezav S, ki vsebuje vse povezave grafa,
• dokler je S neprazen in v F nimamo vpetega drevesa:
• iz nabora S odstranimo povezavo z najmanjšo težo,
• če ta povezava povezuje dve različni drevesi, jo dodamo v drevo F - iz dveh dreves tako ustvarimo eno,
• sicer povezavo zavržemo.

Če ima ob zaključku algoritma gozd eno samo drevo, je to drevo minimalno vpeto drevo povezanega grafa.

Kruskalov algoritem se da implementirati s podatkovno strukturo zlivanja z iskanjem oz. union find. Do treh različic te strukture lahko pridemo kot gost na Spletni učilnici FMF za leto 2010/11.

Uporabil sem UFA različico. V tej podatkovni strukturi UnionFind so točke označene od 0 do n-1, kjer n predstavlja število vozlišč. Ta podatek hranimo v konstruktorju razreda. Ob začetnem vnosu imamo n vozlišč in n dreves – vsako vozlišče je drevo zase.
V razredu hranimo metode:

• count: vrne nam število dreves v grafu;
• find: podamo vozlišče p, vrne nam število na (p-1)-tem mestu. Vozlišča, kjer find vrne isto število, ležijo v istem drevesu oz. so povezane;
• connected: za dve vozlišči preverimo, če sta povezani;
• union: povežemo vozlišči, če še nista, in zmanjšamo število dreves za ena.
  S pomočjo te strukture lahko spišemo program Kruskal, kjer vključimo strategijo algoritma iz prejšnje točke. Program prejme dva parametra – v prvem podamo vse povezave v grafu, v drugem pa število vozlišč. Povezave podamo v seznamu, kjer vsaka povezava hrani tri podatke: prvo in drugo vozlišče povezave ter ceno le te. Pri številu vozlišč vnesemo kar celo število, vozlišča pa so poimenovana s številkami od 0 dalje.

V programu iz vnesenega števila vozlišč ustvarimo vozlišča, ki so tipa razreda UnionFind. Povezave uredimo naraščajoče glede na cene. Na koncu bomo vrnili seznam povezav in ceno, zato pred zanko ustvarimo prazen seznam, kamor bomo dodajali dobre povezave in števec, ki mu bomo prištevali vrednosti teh povezav. Nato sestavimo while zanko, ki teče vse dokler ne zmanjka povezav oz. je število dobrih povezav za ena manjše od števila vozlišč. V zanki iz začetka urejenega seznama povezav jemljemo po eno povezavo. Če iz prvega vozlišča povezave še ni poti v drugo vozlišče, potem je povezava dobra – povezavo dodamo v seznam dobrih povezah, vozlišči povežemo z metodo union in skupni ceni prištejemo ceno povezave. Če imamo po izteku zanke eno samo drevo, je to drevo vpeto. To lahko preverimo s pomočjo metode count.

Časovna zahtevnost Kruskalovega algoritma je oz. .
je največ in , se pravi je .

Primer 1 Preverimo pravilnost delovanja našega programa na primeru, ki ga najdemo na spletni strani, kjer je opisan Kruskalov algoritem z zgledom.

Dan je graf G, odebeljene povezave tvorijo minimalno vpeto drevo.

Povezave s pripadajočimi cenami vnesemo v seznam, ki ga nato kličemo s programom Kruskal, kjer podamo še število vozlišč.

Kot vidimo se dobljena rešitev s programom Kruskal malo razlikuje od rešitve iz dane spletne strani, rešitev pa je ravno tako pravilna - ceni obeh minimalnih dreves sta namreč isti.

Razlika med rešitvama je zato, ker je naš program najprej obravnaval povezavo (3,5), na spletni strani pa je pod sliko razvidno, da je bila pred povezavo (3,5) obravnavana povezava (5,6). Iz našega programa je tudi razvidno, da deluje požrešno in tako najprej jemlje cenejše povezave.



Primer 2 Preverimo še delovanje programa Kruskal na večjih grafih.

Ker je težko spremljati vnašanje vseh teh povezav, je smiselno ob vnašanju sproti označevati (npr. v slikarju, na list papirja) katere povezave smo že vnesli.

Program nam vrne isto težo, tudi minimalni vpeti drevesi sta isti.

• Wikipedia
• Spletna učilnica FMF - algoritmi Union Find
• Spletna učilnica FMF - ideja za Kruskalov algoritem s pomočjo podatkovne strukture Union Find
• O algoritmu, primer delovanja
• primer MVD