Video: Razlika Med Kruškalom In Prim
2024 Avtor: Mildred Bawerman | [email protected]. Nazadnje spremenjeno: 2023-12-16 08:42
Kruskal vs Prim
V računalništvu sta Primov in Kruskalov algoritem požrešen algoritem, ki najde povezano drevo za povezani uteženi neusmerjeni graf. Obsegajoče drevo je podgraf grafa, tako da je vsako vozlišče grafa povezano s potjo, ki je drevo. Vsako razponjeno drevo ima težo, najmanjša možna teža / strošek vseh razponjenih dreves pa je minimalno razponsko drevo (MST).
Več o Primovem algoritmu
Algoritem je razvil češki matematik Vojtěch Jarník leta 1930, kasneje pa samostojno računalnik Robert C. Prim leta 1957. Ponovno ga je odkril Edsger Dijkstra leta 1959. Algoritem je mogoče navesti v treh ključnih korakih;
Glede na povezani graf z n vozlišči in ustrezno težo vsakega roba, 1. Izberite poljubno vozlišče iz grafa in ga dodajte drevesu T (ki bo prvo vozlišče)
2. Upoštevajte uteži vsakega roba, povezanega z vozlišči v drevesu, in izberite najmanjšo vrednost. Dodajte rob in vozlišče na drugem koncu drevesa T in rob odstranite z grafa. (Izberite katerega koli, če obstajata dva ali več minimumov)
3. Ponavljajte 2. korak, dokler drevesu ne dodate robov n-1.
Pri tej metodi se drevo začne z enim poljubnim vozliščem in se od tega vozlišča naprej širi z vsakim ciklom. Za pravilno delovanje algoritma mora biti torej graf povezan graf. Osnovna oblika Primovega algoritma ima časovno zapletenost O (V 2).
Več o Kruškalovem 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 težo vsakega roba, 1. Izberite lok z najmanjšo težo celotnega grafa in ga dodajte drevesu ter ga izbrišite z grafa.
2. Od preostalih izberite najmanj ponderiran rob na način, ki ne tvori cikla. Dodajte rob drevesu in ga izbrišite iz grafa. (Izberite katerega koli, če obstajata dva ali več minimumov)
3. Postopek ponovite v 2. koraku.
Pri tej metodi se algoritem začne z najmanj tehtanim 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 inicializira 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 prim algoritmu mora biti graf povezan graf, medtem ko lahko Kruskal-ov deluje tudi na nepovezanih grafih.
• Primov algoritem ima časovno kompleksnost O (V 2), Kruskalova časovna zahtevnost pa O (logV).
Priporočena:
Razlika Med Konfliktom Med Skupinami In Znotraj Skupine
Ključna razlika med konfliktom med skupinami in znotraj skupine je, da se konflikt med skupinami nanaša na spor med dvema ali več skupinami, medtem ko
Razlika Med Apnejo Med Spanjem In Smrčanjem
Ključna razlika - apneja v spanju proti smrčanju Ključna razlika med apnejo v spanju in smrčanjem je, da je apneja v spanju motnja spanja, za katero je značilna premor
Razlika Med Odnosi Med Delodajalci In Delojemalci
Industrijski odnosi vs odnosi z zaposlenimi Večina od nas misli, da vemo, kaj so industrijski odnosi. Študija zaposlovanja in trga dela je tisto, kar m
Razlika Med Preverjeno Izjemo In Izjemo Med Izvajanjem
Izjeme Checked Exception vs Runtime Exception so posebne vrste dogodkov, ki lahko motijo normalen potek programa. Izjema imena izhaja iz »exc
Razlika Med Komunikacijo Med živalmi In človekom
Komunikacija med živalmi in človekom Prenos pomembnih informacij je znan kot komunikacija in je bil sestavni del uspeha, zato