Kruskal vs Prim
Arvutiteaduses on Primi ja Kruskali algoritmid ahned algoritmid, mis leiavad ühendatud kaalutud suunamata graafi jaoks minimaalse ulatuva puu. Läbiv puu on graafi alamgraaf nii, et graafi iga sõlme ühendab rada, milleks on puu. Igal sirutuspuul on kaal ja kõigi laienevate puude minimaalne võimalik kaal / maksumus on minimaalne laiuspuu (MST).
Lisateave Primi algoritmi kohta
Algoritmi töötas välja Tšehhi matemaatik Vojtěch Jarník 1930. aastal ja hiljem iseseisvalt arvutiteadlane Robert C. Prim aastal 1957. Selle avastas uuesti Edsger Dijkstra 1959. Algoritmi saab öelda kolmes põhietapis;
Arvestades ühendatud graafi, kus on n sõlme ja iga serva vastavat kaalu, 1. Valige graafikult meelevaldne sõlm ja lisage see puule T (mis on esimene sõlm)
2. Võtke arvesse iga puu sõlmedega ühendatud servade kaalu ja valige miinimum. Lisage puu T teine ots ja sõlm ja eemaldage graafilt serv. (Valige ükskõik milline, kui on olemas vähemalt kaks miinimumi)
3. Korrake 2. sammu, kuni puule lisatakse n-1 serva.
Selles meetodis algab puu ühe suvalise sõlmega ja laieneb sellest tsüklist alates edasi. Seega peab algoritmi korralikuks toimimiseks graafik olema ühendatud graafik. Primi algoritmi põhivormil on aja (O 2) keerukus.
Lisateave Kruskali algoritmi kohta
Joseph Kruskali väljatöötatud algoritm ilmus Ameerika Matemaatika Seltsi töös 1956. aastal. Kruskali algoritmi saab väljendada ka kolme lihtsa sammuna.
Võttes arvesse n sõlme ja iga serva vastavat kaalu, 1. Valige kaar, millel on kogu graafiku väikseim kaal, lisage puule 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. (Valige ükskõik milline, kui on olemas vähemalt kaks miinimumi)
3. Korrake protsessi 2. etapis.
Selles meetodis algab algoritm kõige vähem kaalutud servaga ja jätkab iga tsükli iga serva valimist. Seetõttu ei pea algoritmis graafikut ühendama. Kruskali algoritmil on aja keerukus O (logV)
Mis vahe on Kruskali ja Primi algoritmil?
• Primi algoritm lähtestatakse sõlmega, Kruskali algoritm aga servaga.
• Prim'i algoritmid ulatuvad ühest sõlmest teise, samal ajal kui Kruskali algoritm valib servad nii, et serva asukoht ei põhine viimasel etapil.
• Prim'i algoritmis peab graafik olema ühendatud graafik, samas kui Kruskali funktsioonid võivad toimida ka lahtiühendatud graafikutel.
• Prim'i algoritmil on aja keerukus O (V 2) ja Kruskali aja keerukus on O (logV).
