Razlika između Kruskala i Prim
Share
Kruskal vs Prim
U računalnoj znanosti, Primov i Kruskalov algoritam su pohlepni algoritam koji pronalazi minimalno raspon stabla za spojeni ponderirani neizravni graf. Obuhvatno stablo je podgraf grafikona, tako da je svaki čvor grafikona povezan stazom, koja je stablo. Svako stablo opruge ima težinu, a najmanja moguća težina / trošak svih opružnih stabala je minimalno rasporeno drvo (MST).
Više o Primovu algoritmu
Algoritam je razvio češki matematičar Vojtěch Jarník 1930. godine, a kasnije neovisno računalni znanstvenik Robert C. Prim 1957. godine. Ponovno ga je otkrio Edsger Dijkstra 1959. Algoritam se može navesti u tri ključna koraka;
S obzirom na povezani grafikon s n čvorova i odgovarajućom težinom svakog ruba,
1. Odaberite proizvoljni čvor s grafikona i dodajte ga u stablo T (koje će biti prvi čvor)
2. Razmislite o težini svakog ruba spojenog s čvorovima na 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. Ponovite korak 2 dok se n-1 rubovi ne dodaju u stablo.
U ovoj metodi, stablo započinje jednim proizvoljnim čvorom i širi se od tog čvora nadalje sa svakim ciklusom. Dakle, da bi algoritam pravilno radio, graf mora biti povezan grafikon. Osnovni oblik algoritma Prim ima vremensku složenost od O (V2).
Više o Kruskalovom algoritmu
Algoritam koji je razvio Joseph Kruskal pojavio se u zbornicima Američkog matematičkog društva 1956. Kruskalov algoritam također se može izraziti u tri jednostavna koraka.
S obzirom na grafikon s n čvorova i odgovarajućom težinom svakog ruba,
1. Odaberite luk s najmanjom težinom cijelog grafikona i dodajte ga u stablo i izbrišite s grafikona.
2. Od preostalog odaberite najmanje ponderirani rub, na način koji ne tvori ciklus. Dodajte rub stablu 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 s odabirom svakog ruba u svakom ciklusu. Prema tome, 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 se Kruskalov algoritam pokreće s rubom.
• Primovi algoritmi rasponu od jednog čvora do drugog, dok Kruskalov algoritam bira rubove na način da se položaj ruba ne temelji na zadnjem koraku.
• U Primovom algoritmu graf mora biti povezan grafikon, dok Kruskalovi mogu funkcionirati i na nepovezanim grafovima.
• Primov algoritam ima vremensku složenost od O (V2), a Kruskalova vremenska složenost je O (logV).
