Kruskal vs Prim
U informatici, Primovi i Kruskalovi algoritmi su pohlepni algoritam koji pronalazi minimalno razapinjuće stablo za povezani ponderisani neusmjereni graf. Razdvojno stablo je podgraf grafa takav da je svaki čvor grafa povezan putem, što je stablo. Svako razapinjuće stablo ima težinu, a minimalna moguća težina/trošak 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 nezavisno kompjuterski naučnik Robert C. Prim 1957. godine. Ponovo ga je otkrio Edsger Dijkstra 1959. Algoritam se može navesti u tri ključna koraka;
S obzirom na povezani graf sa n čvorova i odgovarajuću težinu svake ivice, 1. Odaberite proizvoljni čvor sa grafa i dodajte ga stablu T (koje će biti prvi čvor)
2. Uzmite u obzir težine svake ivice povezane sa čvorovima u stablu i odaberite minimum. Dodajte rub i čvor na drugom kraju stabla T i uklonite rub iz grafa. (Odaberite bilo koji ako postoje dva ili više minimuma)
3. Ponovite korak 2, sve dok se stablu ne doda n-1 ivica.
U ovoj metodi, stablo počinje sa 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 od O(V2).
Više o Kruskalovom algoritmu
Algoritam koji je razvio Joseph Kruskal pojavio se u radu Američkog matematičkog društva 1956. Kruskalov algoritam se takođe može izraziti u tri jednostavna koraka.
Dat je graf sa n čvorova i odgovarajućom težinom svake ivice, 1. Odaberite luk s najmanjom težinom cijelog grafa i dodajte u stablo i izbrišite iz grafa.
2. Od preostalih izaberite najmanju ivicu, na način da ne formira ciklus. Dodajte ivicu stablu i izbrišite iz grafa. (Odaberite bilo koji ako postoje dva ili više minimuma)
3. Ponovite postupak u koraku 2.
U ovoj metodi, algoritam počinje sa najmanje ponderisanom ivicom i nastavlja da bira svaku ivicu u svakom ciklusu. Dakle, 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 se inicijalizira čvorom, dok Kruskalov algoritam inicira ivicom.
• Primovi algoritmi se protežu od jednog čvora do drugog, dok Kruskalov algoritam bira rubove na način da pozicija ivice nije zasnovana na posljednjem koraku.
• U Prim algoritmu, graf mora biti povezan graf, dok Kruskal može funkcionirati i na nepovezanim grafovima.
• Primov algoritam ima vremensku složenost O(V2), a Kruskalova vremenska složenost je O(logV).
