2 Replies Latest reply on Dec 15, 2009 2:36 PM by 843853

# General Algorithm Question

This is a general programming algorithm question opposed to specifc java based but i hope you can help

How can we say Prims algorithm is betetr than Kruskal or visa versa when their time complexitys are different

O(n log n) - Kruskal
O(n^2) - Prim

I appreciate it has something to do with whether the graph is sparse or dence but cant find any resources to aid me in understanding this

So far my understanding is that a dence graph is best suited to Prim as it sequentially finds the next route based on
1) node being unused
2)less weight than any other path

However with Kruskel its a greedy algorithm, essentially adding all weights and connections to a heap <? not sure about that> and selecting each cheapest path until all nodes are used. It has no view to the bigger picture wich makes it a little naieve and thus better for sparse graphs

so basically back to the question, how can the 2 be compared for situations where 1 is betetr than the other or where there is a case that the 2 may not differ tooo much from each other

thanks