Prim’s Algorithm

Hello people…! In this post, I will talk about the Prim’s Algorithm for finding a Minimum Spanning Tree for a given weighted graph. It is an excellent example of a Greedy Algorithm. It is very similar to Dijkstra’s Algorithm for finding the shortest path from a given source. This is my first post regarding the minimum spanning tree, so, let’s take some time to learn what a minimum spanning tree is.

Minimum Spanning Tree – A spanning tree is a connected and acyclic graph. It has |V| – 1 edges. For a given graph, we could have many spanning trees. A minimum spanning tree is the one which has the minimum sum of all edges when compared to all the possible spanning trees that can be formed from the given graph.

Why would anyone bother about a minimum spanning tree..? Minimum spanning trees are used in certain places to get the job done faster. It is used in a network router to find the routes to other components in the network such that the transfer of a data packet would consume the least amount of resources. Minimum spanning trees are used in a whole lot of other aspects of computer science. So, let’s get started !

If you already know Dijkstra’s Algorithm, you could relate to the similarities between these two algorithms. But, let’s assume that you don’t know Dijkstra’s Algorithm, and begin Prim’s Algorithm from scratch. Before we get started with the algorithm, let’s look at the tools we would be needing –

• Priority Queue – We will be using a Binary Min-Heap with an array-based implementation with a small twist. The array here will be an STL vector. This is because, during the course of our algorithm, this priority queue will grow and shrink.
• Visited array – We will be using a Boolean array of size |V| to keep a check on which nodes have been visited and which haven’t been visited.
• Extra Adjacency List – Beside the input Adjacency List, we will have another empty Adjacency List where we will keep filling it with vertices. This will become our final minimum spanning tree.

Beside these, we will use other variables to aid our algorithm, but these are our main tools. Now, let’s look at a crude step-by-step version of the Prim’s Algorithm –

• Start from any arbitrary vertex.
• Note down all the edges emerging from this vertex.
• Mark this edge as visited.
• Select an edge with the minimum weight.
• Traverse to the other end. Remove this edge from the list and insert it into the minimum spanning tree.
• Repeat this process for the newly visited vertex.
• Each time you visit a vertex, check if it was already visited, only then we do the process of adding its edges to the list and picking the minimum.
• If not, then simply pick up the next minimum edge.
• Repeat this process until all the nodes are visited.

This is the raw idea of the Prim’s Algorithm. Now, I hope you can figure out the why we would need the tools I stated above. The list into which we are adding edges is our priority queue. We will be adding and removing edges into it as we move forward in the algorithm. We will be adding the edges into the minimum spanning tree, so we need the extra adjacency list. To check whether a vertex has been visited or not, we will need the Boolean array.

But there’s another thing of interest from the coding point of view. It is stated that if we come to a vertex that we have already visited, we extract the next minimum from our list (priority queue). But, this edge could be connecting two vertices which the current vertex may not be a part of. Think about this for a while ! It is not enough if we simply keep inserting edge weights into the list. We must be precisely be able to recognize an edge from the rest. Therefore, we must store all the attributes that an edge has. Which are –

• Start vertex.
• End vertex.
• Weight.

So, this tells something about our priority queue. Each element in the priority queue must be a struct of these three integers. So, our priority queue would be a vector of structures, where the structure looks like this –

It denotes that there is an edge u → v, with a weight of ‘weight’. Now, keep reading the step-by-step process till you are comfortable with the idea. And now, let’s refine our idea of Prim’s Algorithm by writing the pseudo-code –

Or, if we put the same thing in much simpler English –

I hope the pseudo-code gives you an idea of what is to be done in Prim’s Algorithm. If not, feel free to ask your doubts..! To understand the working of the algorithm, let’s take up an sample graph and apply the above algorithm. The sketch below applies the Prim’s Algorithm on a given graph to compute the Minimum Spanning Tree –

I hope the sketch makes it clear how the Prim’s Algorithm works. Feel free to ask, if you have any doubts…!

The Priority Queue

Now, coming to the programming part of the Prim’s Algorithm, we need a priority queue. There are many ways to implement a priority queue, the best being a Fibonacci Heap. But, we will keep it simple and go for a Min – Heap. Now. As stated before, we need each node in the heap to store information about the startVertex, endVertex and the weight of the edge. So, we will use an array based implementation of the Min Heap, where the array will be an array of structures, where the priorities are based on edge weights. So, code for the priority queue goes in that fashion.

Other implementations of Prim’s Algorithm

• Prim’s Algorithm using C++ STL

All I did was I took the code in my post regarding Binary Heaps, and modified it to work on an array of structures. And I added a new function ExtractMin() which returns the element with the minimum priority, essentially deleting it from the Min Heap. Go through the code of the Priority Queue until you get comfortable with it. You could add a main function to test the code and know for yourself how it works. It would be even better if you took your own (or mine) implementation of Binary Heap and modified it to support Prim’s Algorithm on your own.

The Algorithm

Once you have your Priority Queue ready, it is pretty easy to code the Prim’s Algorithm looking at the pseudo-code. But there is one coding issue. The Priority Queue here is an array, which obviously must be of fixed length. But in the algorithm, the edges are continuously added and extracted from the queue. So, what should our array size be….? If you notice, throughout the algorithm, we add every edge at most twice. So, the maximum possible size of the queue would be 2 ✗ |E|. So, you could keep the array size as this, or, you could optimize the algorithm by ensuring that an edge is not inserted twice. This will increase your efficiency in terms of memory usage and computations. But how do you do this..? While adding an edge, check if it is leading to a vertex which has already been visited. If not, only then we insert it into the Min Heap. Well, first try to code it without the optimization, if you succeed then optimizing it shouldn’t be difficult. If you get stuck, you can refer to my code below, which is the optimized version…!

If not for the Boolean array, everything else is C. So, this code shouldn’t look alien to you. This was the Prim’s Algorithm. Now, let’s talk about the complexity –

• We perform at most |E| insert operations into the Min Heap, where each costs O(log |E|), so that makes up, O(|E| log |E|).
• We perform at most |E| extract min operations, where each costs O(log |E|), so that makes up, O(|E| log |E|).

So, the worst case complexity of the Prim’s Algorithm is O(|E| log |E|), which is okay, but not great if the given graph is a dense graph, where |E| would be in the order of |V|². The algorithm can be optimized further to improve the complexity to O(|E| log |V|), using a Min Heap as the Priority Queue itself. We will discuss that implementation shortly.

I hope my post has helped you in getting started with the Prim’s Algorithm. If it did, let me know by commenting…! Keep practising… Happy Coding…! 🙂