Kruskal vs Prim
Arvutiteaduses on Primi ja Kruskali algoritmid ahne algoritm, mis leiab ühendatud kaalutud suunamata graafiku jaoks minimaalse ulatuva puu. Ulatuspuu on graafi alamgraaf, nii et iga graafi sõlm on ühendatud teega, mis on puu. Igal ulatuval puul on kaal ja kõigi toestavate puude minimaalne võimalik kaal/kulu on minimaalne ulatuspuu (MST).
Lisateavet Primi algoritmi kohta
Algoritmi töötas välja Tšehhi matemaatik Vojtěch Jarník 1930. aastal ja hiljem iseseisv alt arvutiteadlane Robert C. Prim 1957. aastal. Edsger Dijkstra avastas selle uuesti 1959. aastal. Algoritmi saab esitada kolmes võtmeetapis;
Arvestades n sõlmega ühendatud graafikut ja iga serva vastavat kaalu, 1. Valige graafikult suvaline sõlm ja lisage see puusse T (mis on esimene sõlm)
2. Võtke arvesse iga puu sõlmedega ühendatud serva raskust ja valige miinimum. Lisa serv ja sõlm puu teises otsas T ning eemalda serv graafikult. (Kui on kaks või enam miinimumi, valige ükskõik milline)
3. Korrake 2. sammu, kuni puule on lisatud n-1 serva.
Selle meetodi puhul algab puu ühe suvalise sõlmega ja laieneb sellest sõlmest iga tsükliga edasi. Seega, et algoritm korralikult töötaks, peab graafik olema ühendatud graafik. Primi algoritmi põhivormi ajaline keerukus on O(V2).
Lisateavet Kruskali algoritmi kohta
Joseph Kruskali välja töötatud algoritm ilmus Ameerika Matemaatika Seltsi toimetistes 1956. aastal. Kruskali algoritmi saab väljendada ka kolme lihtsa sammuga.
Arvestades n sõlmega graafikut ja iga serva vastavat kaalu, 1. Valige kogu graafiku väikseima raskusega kaar ja lisage puusse ja kustutage graafikult.
2. Ülejäänud hulgast valige kõige vähem kaalutud serv viisil, mis ei moodusta tsüklit. Lisage puule serv ja kustutage graafikult. (Kui on kaks või enam miinimumi, valige ükskõik milline)
3. Korrake toimingut punktis 2.
Selle meetodi puhul algab algoritm vähima kaalutud servaga ja jätkab iga serva valimist igas tsüklis. Seetõttu ei pea graafik algoritmis olema ühendatud. Kruskali algoritmi ajaline keerukus on O(logV)
Mis vahe on Kruskali ja Primi algoritmil?
• Primi algoritm initsialiseerub sõlmega, Kruskali algoritm aga servaga.
• Primi algoritmid ulatuvad ühest sõlmest teise, samas kui Kruskali algoritm valib servad nii, et serva asukoht ei põhine viimasel sammul.
• Primi algoritmis peab graafik olema ühendatud graaf, samas kui Kruskal saab toimida ka lahtiühendatud graafikutel.
• Primi algoritmi ajaline keerukus on O(V2) ja Kruskali ajaline keerukus on O(logV).
