Prim’s Algorithm

In the Graph Theory, Prim’s algorithm creates an optimal spanning tree. I will show here my implementation of this algorithm. It is used in the Graph Lib that I showed you earlier. I don’t pretend that it is done the best way, but it’s working completely.

We create a copy of our vertices & edges because we are going to manipulate this collections and we do not want this to affected our graph. Well, let’s begin constructing our optimal spanning tree. We need a root vertex for this tree and I am going to use the first vertex in the collection. Remove it and add it to the tree.

We are performing next steps until out collection of vertices is empty.

In every loop we have to find an optimal edge with one vertex in the tree vertices and other in the vertices collection. When we find it (and we must find it!) we add this edge and the vertex (which was not in the tree vertices collection) to the tree.

So, that’s it! We have an optimal (max or min) spanning tree, constructed using the Prim’s algorithm. I have shown an example in my post for the Graph Lib. If you have any recommendations about this implementation, feel free to say them.

If you like this post, share it with your fellows
    • inslayn

      Thanks! Very clear explanation. I’m not using your method, but your explanation helped me to figure out what was going wrong with my implementation. Thanks again 🙂