Kruskal vs Prim
U računalnoj znanosti, Primov i Kruskalov algoritam su pohlepni algoritam koji pronalazi minimalno razapinjuće stablo za povezani težinski neusmjereni graf. Razapinjuće stablo je podgraf grafa tako da je svaki čvor grafa povezan stazom, koja je stablo. Svako razapinjuće stablo ima težinu, a minimalne moguće težine/cijena svih razapinjućih stabala je minimalno razapinjuće stablo (MST).
Više o Primovom algoritmu
Algoritam je razvio češki matematičar Vojtěch Jarník 1930., a kasnije neovisno računalni znanstvenik Robert C. Prim 1957. Ponovno ga je otkrio Edsger Dijkstra 1959. Algoritam se može opisati u tri ključna koraka;
S obzirom na povezani graf s n čvorova i odgovarajuću težinu svakog ruba, 1. Odaberite proizvoljan čvor s grafa i dodajte ga stablu T (koje će biti prvi čvor)
2. Razmotrite težine svakog ruba povezanog s čvorovima u stablu i odaberite minimum. Dodajte rub i čvor na drugom kraju stabla T i uklonite rub s grafa. (Odaberite bilo koji ako postoje dva ili više minimuma)
3. Ponovite korak 2, dok se stablu ne doda n-1 rubova.
U ovoj metodi, stablo počinje s jednim proizvoljnim čvorom i širi se od tog čvora nadalje sa svakim ciklusom. Dakle, da bi algoritam ispravno radio, graf mora biti povezan graf. Osnovni oblik Primovog algoritma ima vremensku složenost O(V2).
Više o Kruskalovom algoritmu
Algoritam koji je razvio Joseph Kruskal pojavio se u zborniku radova Američkog matematičkog društva 1956. Kruskalov algoritam također se može izraziti u tri jednostavna koraka.
S obzirom na graf s n čvorova i odgovarajuću težinu svakog ruba, 1. Odaberite luk s najmanjom težinom cijelog grafa i dodajte u stablo i izbrišite iz grafa.
2. Od preostalih odaberite rub s najmanjom težinom, na način da ne formirate ciklus. Dodajte rub stablu i izbrišite iz grafikona. (Odaberite bilo koji ako postoje dva ili više minimuma)
3. Ponovite postupak u koraku 2.
U ovoj metodi, algoritam počinje s najmanje ponderiranim rubom i nastavlja birati svaki rub u svakom ciklusu. Stoga u algoritmu graf ne mora biti povezan. Kruskalov algoritam ima vremensku složenost od O(logV)
Koja je razlika između Kruskalovog i Primovog algoritma?
• Primov algoritam inicijalizira s čvorom, dok Kruskalov algoritam inicira s rubom.
• Primovi algoritmi protežu se od jednog čvora do drugog dok Kruskalov algoritam odabire rubove na način da se položaj ruba ne temelji na zadnjem koraku.
• U primovom algoritmu, graf mora biti povezan graf dok Kruskalov može funkcionirati i na nepovezanim grafovima.
• Primov algoritam ima vremensku složenost O(V2), a Kruskalova vremenska složenost je O(logV).
