CODEWITHSUNDEEP
calgorithmminimum-spanning-treeprims-algorithmkruskals-algorithm
bubblellicious
bubblellicious

Reputation:

How to turn Prim's algorithm into Kruskal's algorithm?

I've implemented Prim's algorithm in C (www.bubblellicious.es/prim.tar.gz) but I was just wondering how to transform this into Kruskal's algorithm.

It seems they're quite similar, but I can't imagine how can I modify my old code into that new one. It'd be delicious if you give some advices or something. I know that's easy, but I'm still a n00b in C programming ...

Upvotes: 0

Views: 2020

Answers (3)

RED SOFT ADAIR
RED SOFT ADAIR

Reputation: 12238

Why dont you consider switching to C++ and using the boost graph library (http://www.boost.org/)?

It contains very well implementations for both algorithms. Type-safe and highly performant. See kruskal_minimum_spanning_tree and prim_minimum_spanning_tree

Upvotes: 0

jilles de wit
jilles de wit

Reputation: 7148

To convert you need a forest (i.e. a set of trees where initially each node is a tree) as your temporary output structure rather than a single tree. Then on each step, rather than finding the cheapest vertex that adds a currently unconnected node to your tree, you find the cheapest edge in the graph and, if it creates a new tree (i.e. connects two previously unconnected nodes) add that tree to the forest and remove the source trees. Otherwise discard the edge. A proper implementation of Kruskal is more memory intensive but less time intensive than a proper Prim implementation.

But the differences between the two are quite large. Probably all you can keep between are some helper functions and some data structures. Not a conversion, more a rewrite using more high level building blocks.

Upvotes: 1

Pod
Pod

Reputation: 4129

Why not just write Kruskal's from scratch and see how they compare in your own solutions? Best way to learn.

Upvotes: 5

Related Questions