Razlika med Kruskalom in Prim
Share
Kruskal proti Prim
V računalništvu sta algoritem Prim in Kruskal pohlepna algoritma, ki najdeta minimalno vpeto drevo za povezan tehtani neizmerjeni graf. Vpeto drevo je podgraf grafa, tako da je vsako vozlišče grafa povezano s potjo, ki je drevo. Vsako razpokano drevo ima težo, najmanjša možna teža / stroški vseh vpetih dreves pa je najmanjša vretena (MST).
Več o Primovem algoritmu
Algoritem je razvil češki matematik Vojtěch Jarník leta 1930, kasneje pa neodvisno računalničar, Robert C. Prim leta 1957. Na novo ga je odkril Edsger Dijkstra leta 1959. Algoritem je mogoče navesti v treh ključnih korakih;
Glede na povezan graf z n vozlišči in ustrezno maso vsakega roba,
1. Iz grafa izberite poljubno vozlišče in ga dodajte v drevo T (ki bo prvo vozlišče)
2. Razmislite o uteži vsakega roba, povezanega z vozlišči na drevesu, in izberite najmanjšo. Dodajte rob in vozlišče na drugem koncu drevesa T in odstranite rob s grafa. (Izberite katero koli, če obstajata dve ali več minimalnih vrednosti)
3. Ponovite korak 2, dokler n-1 robovi ne dodate drevesa.
Pri tej metodi se drevo začne z enim poljubnim vozliščem in se iz tega vozlišča širi z vsakim ciklom. Zato mora biti za pravilno delovanje algoritma graf povezan graf. Osnovna oblika algoritma Prim ima časovno zapletenost O (V2).
Več o Kruskalovem algoritmu
Algoritem, ki ga je razvil Joseph Kruskal, se je pojavil v zborniku Ameriškega matematičnega društva leta 1956. Kruskalov algoritem lahko izrazimo tudi v treh preprostih korakih.
Glede na graf z n vozlišči in ustrezno maso vsakega roba,
1. Izberite lok z najmanjšo težo celotnega grafa in ga dodajte v drevo ter ga izbrišite.
2. Od preostalih izberite najmanj uteženi rob na način, ki ne tvori cikla. Dodajte rob drevesu in izbrišite iz grafa. (Izberite katero koli, če obstajata dve ali več minimalnih vrednosti)
3. Ponovite postopek v koraku 2.
Pri tej metodi se algoritem začne z najmanj obteženim robom in nadaljuje z izbiro vsakega roba v vsakem ciklu. Zato v algoritmu grafa ni treba povezati. Kruskalov algoritem ima časovno zapletenost O (logV)
Kakšna je razlika med Kruskalovim in Primovim algoritmom?
• Primov algoritem se inicijalizira z vozliščem, medtem ko se Kruskalov algoritem začne z robom.
• Primovi algoritmi segajo od enega vozlišča do drugega, medtem ko Kruskalov algoritem izbere robove tako, da položaj roba ne temelji na zadnjem koraku.
• V Primovem algoritmu mora biti graf povezan graf, Kruskalovi pa lahko delujejo tudi na odklopljenih grafih.
• Primov algoritem ima časovno kompleksnost O (V2), Kruskaljeva časovna zapletenost pa je O (logV).
