Kruskal vs Prim
U računalnoj znanosti Primov i Kruskalov algoritmi pohlepni su algoritam koji pronalazi minimalno rasponično stablo za povezani ponderirani neusmjereni graf. Rasprostranjeno stablo je podgraf grafa takav da je svaki čvor grafa povezan stazom koja je stablo. Svako rasponsko stablo ima težinu, a minimalna moguća težina / trošak svih rastegljivih stabala je minimalno rastezljivo stablo (MST).
Više o Primovom algoritmu
Algoritam je razvio češki matematičar Vojtěch Jarník 1930. godine, a kasnije neovisno informatičar Robert C. Prim 1957. godine. Ponovno ga je otkrio Edsger Dijkstra 1959. Algoritam se može iznijeti u tri ključna koraka;
S obzirom na povezani graf s n čvorova i odgovarajuću težinu svakog ruba, 1. Odaberite proizvoljni čvor s grafa i dodajte ga na stablo T (koji će biti prvi čvor)
2. Uzmite u obzir težine svakog ruba spojenog na čvorove u stablu i odaberite minimum. Dodajte rub i čvor na drugom kraju stabla T i uklonite rub s grafikona. (Odaberite bilo koji ako postoje dva ili više minimuma)
3. Ponavljajte korak 2 dok se stablo ne doda n-1 rubovi.
U ovoj metodi stablo započinje jednim proizvoljnim čvorom i širi se od tog čvora dalje sa svakim ciklusom. Stoga, da bi algoritam mogao ispravno raditi, graf mora biti povezani graf. Osnovni oblik Primova algoritma ima vremensku složenost O (V 2).
Više o Kruskalovom algoritmu
Algoritam koji je razvio Joseph Kruskal pojavio se u radu 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 grafikona, dodajte na stablo i izbrišite s grafa.
2. Od preostalih odaberite najmanje ponderirani rub, na način da ne tvori ciklus. Dodajte rub drvetu i izbrišite s grafikona. (Odaberite bilo koji ako postoje dva ili više minimuma)
3. Ponovite postupak u koraku 2.
U ovoj metodi algoritam započinje s najmanje ponderiranim rubom i nastavlja odabir svakog ruba u svakom ciklusu. Stoga u algoritmu graf ne mora biti povezan. Kruskalov algoritam ima vremensku složenost O (logV)
Koja je razlika između Kruskalovog i Priminog algoritma?
• Primov algoritam inicijalizira se čvorom, dok Kruskalov algoritam započinje rubom.
• Primovi algoritmi obuhvaćaju jedan čvor, dok Kruskalov algoritam odabire rubove na način da se položaj ruba ne temelji na posljednjem 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 (V 2), a Kruskalova vremenska složenost je O (logV).
