Implementing Kruskal's algorithm in Ada, not sure where to start

Question

With reference to Kruskal's algorithm in Ada, I'm not sure where to start.

I'm trying to think through everything before I actually write the program, but am pretty lost as to what data structures I should be using and how to represent everything.

My original thought is to represent the full tree in an adjacency list, but reading Wikipedia the algorithm states to create a forest F (a set of trees), where each vertex in the graph is a separate tree and I'm not sure how to implement this without getting really messy quickly.

The next thing it says to do is create a set S containing all the edges in the graph, but once again I'm not sure what the best way to do this would be. I was thinking of an array of records, with a to, from and weight, but I'm lost on the forest.

Lastly, I'm trying to figure out how I would know if an edge connects two trees, but again am not sure what the best way to do all of this is.

Answer 1

I can see where their algorithm description would leave you confused as how to start. It left me the same way.

I'd suggest reading over the later Example section instead. That makes it pretty clear how to proceed, and you can probably come up with the data structures you would need to do it just from that.

It looks like the basic idea is the following:

• Take the graph, find the shortest edge that introduces at least one new vertex, and put it in your "spanning tree".
• Repeat the step above until you have every vertex.

Answer 2

The "create a forest part" really means: implement the pseudocode from the page Disjoint-set data structure. If you can read C++, then I have a pretty straightforward implementation here. (That implementation works, I've used it to implement Kruskal's algo myself :)