Algorithms For Dummies


Determining which algorithm works best



Download 7,18 Mb.
Pdf ko'rish
bet334/651
Sana15.07.2021
Hajmi7,18 Mb.
#120357
1   ...   330   331   332   333   334   335   336   337   ...   651
Bog'liq
Algorithms

Determining which algorithm works best

Both Prim’s and Kruskal’s algorithms output a single connected component, join-

ing all the vertexes in the graph by using the least (or one of the least) long 

sequences of edges (a minimum spanning tree). By summing the edge weights, 

you can determine the length of the resulting spanning tree. Because both algo-

rithms always provide you with a working solution, you must rely on running 

time and decide whether they can take on any kind of weighted graph to deter-

mine which is best.

As for running time, both algorithms provide similar results with Big-O complex-

ity rating of O(E*log(V)), where E is the number of edges and V the number of 

vertexes. However, you must account for how they solve the problem because 

there are differences in the average expected running time.

Prim’s algorithm incrementally builds a single solution by adding edges, whereas 

Kruskal’s algorithm creates an ensemble of partial solutions and aggregates them. 

In creating its solution, Prim’s algorithm relies on data structures that are more 

complex than  Kruskal’s  because it  continuously  adds potential edges as candi-

dates and keeps picking the shortest edge to proceed toward its solution. When 

operating on a dense graph, Prim’s algorithm is preferred over Kruskal’s because 

its priority queue based on heaps does all the sorting jobs quickly and efficiently.



192

 

   


  PART 3 


Download 7,18 Mb.

Do'stlaringiz bilan baham:
1   ...   330   331   332   333   334   335   336   337   ...   651




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2025
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish