Kruskal vs Prim
V računalništvu sta Primova in Kruskalova algoritma požrešen algoritem, ki najde minimalno vpeto drevo za povezan utežen neusmerjen graf. Vpeto drevo je podgraf grafa, tako da je vsako vozlišče grafa povezano s potjo, ki je drevo. Vsako vpeto drevo ima težo in najmanjša možna utež/strošek vseh vpetih dreves je najmanjše vpeto drevo (MST).
Več o Primovem algoritmu
Algoritem je razvil češki matematik Vojtěch Jarník leta 1930 in kasneje neodvisno računalniški znanstvenik Robert C. Prim leta 1957. Ponovno ga je odkril Edsger Dijkstra leta 1959. Algoritem je mogoče opisati v treh ključnih korakih;
Glede na povezan graf z n vozlišči in ustrezno težo vsakega roba, 1. Izberite poljubno vozlišče iz grafa in ga dodajte v drevo T (ki bo prvo vozlišče)
2. Upoštevajte uteži vsakega roba, povezanega z vozlišči v drevesu, in izberite najmanjšo. Dodajte rob in vozlišče na drugem koncu drevesa T in odstranite rob iz grafa. (Izberite katero koli, če obstajata dva ali več minimumov)
3. Ponavljajte 2. korak, dokler drevesu ne dodate n-1 robov.
Pri tej metodi se drevo začne z enim poljubnim vozliščem in se od tega vozlišča širi naprej z vsakim ciklom. Da bi torej algoritem deloval pravilno, mora biti graf povezan graf. Osnovna oblika Primovega algoritma ima časovno kompleksnost O(V2).
Več o Kruskalovem algoritmu
Algoritem, ki ga je razvil Joseph Kruskal, je bil objavljen v zborniku Ameriškega matematičnega društva leta 1956. Kruskalov algoritem je mogoče izraziti 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 v drevo ter izbrišite iz grafa.
2. Od preostalih izberite najmanj obtežen rob, tako da ne tvori cikla. Dodajte rob drevesu in izbrišite iz grafa. (Izberite katero koli, če obstajata dva ali več minimumov)
3. Ponovite postopek v 2. koraku.
Pri tej metodi se algoritem začne z najmanj uteženim robom in nadaljuje z izbiro vsakega roba v vsakem ciklu. Zato v algoritmu grafa ni treba povezati. Kruskalov algoritem ima časovno kompleksnost O(logV)
Kakšna je razlika med Kruskalovim in Primovim algoritmom?
• Primov algoritem se inicializira z vozliščem, medtem ko se Kruskalov algoritem inicializira z robom.
• Primovi algoritmi segajo od enega vozlišča do drugega, medtem ko Kruskalov algoritem izbere robove na način, da položaj roba ne temelji na zadnjem koraku.
• V primovem algoritmu mora biti graf povezan graf, medtem ko Kruskalov lahko deluje tudi na nepovezanih grafih.
• Primov algoritem ima časovno kompleksnost O(V2), Kruskalova časovna kompleksnost pa O(logV).
