Kruskal algorithm implementation in Hell, I don’t know where to start

Question

As for the Kruskal algorithm in Ada, I'm not sure where to start.

I try to think over everything before writing a program, but am rather overlooked as to which data structures I should use and how to represent everything.

My initial thought is to represent a complete tree in an adjacency list, but reading Wikipedia, the algorithm points 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 realize this without becoming really messy.

The next thing he says 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. I was thinking of an array of entries with to , from and weight , but I got lost in the forest .

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

Answer 1

I see where their description of the algorithm will leave you confused how to start. It left me the same way.

I would prefer instead of a later example . This makes it pretty clear how to proceed next, and you can probably come up with data structures that you will need to do just from that.

It seems like the main idea is this:

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

Answer 2

“Creating a part of the forest” really means: implement pseudocode from the Data structure page with unrelated sets . If you can read C ++, then I have a pretty simple implementation here . (This implementation works, I used it to implement Kruskal algo itself :)