Kruskal vs Prim
V računalništvu sta Primov in Kruskalov algoritem požrešen algoritem, ki najde povezano drevo za povezani uteženi neusmerjeni graf. Obsegajoče drevo je podgraf grafa, tako da je vsako vozlišče grafa povezano s potjo, ki je drevo. Vsako razponjeno drevo ima težo, najmanjša možna teža / strošek vseh razponjenih dreves pa je minimalno razponsko drevo (MST).
Več o Primovem algoritmu
Algoritem je razvil češki matematik Vojtěch Jarník leta 1930, kasneje pa samostojno računalnik Robert C. Prim leta 1957. Ponovno ga je odkril Edsger Dijkstra leta 1959. Algoritem je mogoče navesti v treh ključnih korakih;
Glede na povezani graf z n vozlišči in ustrezno težo vsakega roba, 1. Izberite poljubno vozlišče iz grafa in ga dodajte drevesu T (ki bo prvo vozlišče)
2. Upoštevajte uteži vsakega roba, povezanega z vozlišči v drevesu, in izberite najmanjšo vrednost. Dodajte rob in vozlišče na drugem koncu drevesa T in rob odstranite z grafa. (Izberite katerega koli, če obstajata dva ali več minimumov)
3. Ponavljajte 2. korak, dokler drevesu ne dodate robov n-1.
Pri tej metodi se drevo začne z enim poljubnim vozliščem in se od tega vozlišča naprej širi z vsakim ciklom. Za pravilno delovanje algoritma mora biti torej graf povezan graf. Osnovna oblika Primovega algoritma ima časovno zapletenost O (V 2).
Več o Kruškalovem algoritmu
Algoritem, ki ga je razvil Joseph Kruskal, se je pojavil v zborniku Ameriškega matematičnega društva leta 1956. Kruskalov algoritem lahko izrazimo tudi v treh preprostih korakih.
Glede na graf z n vozlišči in ustrezno težo vsakega roba, 1. Izberite lok z najmanjšo težo celotnega grafa in ga dodajte drevesu ter ga izbrišite z grafa.
2. Od preostalih izberite najmanj ponderiran rob na način, ki ne tvori cikla. Dodajte rob drevesu in ga izbrišite iz grafa. (Izberite katerega koli, če obstajata dva ali več minimumov)
3. Postopek ponovite v 2. koraku.
Pri tej metodi se algoritem začne z najmanj tehtanim robom in nadaljuje z izbiro vsakega roba v vsakem ciklu. Zato v algoritmu grafa ni treba povezati. Kruskalov algoritem ima časovno zapletenost O (logV)
Kakšna je razlika med Kruskalovim in Primovim algoritmom?
• Primov algoritem se inicializira z vozliščem, medtem ko se Kruskalov algoritem začne z robom.
• Primovi algoritmi segajo od enega vozlišča do drugega, medtem ko Kruskalov algoritem izbere robove tako, da položaj roba ne temelji na zadnjem koraku.
• V prim algoritmu mora biti graf povezan graf, medtem ko lahko Kruskal-ov deluje tudi na nepovezanih grafih.
• Primov algoritem ima časovno kompleksnost O (V 2), Kruskalova časovna zahtevnost pa O (logV).
