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 –
struct edge { int u; int v; int weight; };
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 –
prims(adjacencyList, vertices, startVertex, MST) current = startVertex for i = 0 to vertices visited[i] = false i = 0 while i < vertices if !visited[current] visited[current] = true temp = adjacencyList[current] while temp != NULL var.u = current var.v = temp->val var.weight = temp->weight PriorityQueue.enqueue(var) temp = temp->next var = PriorityQueue.extractMin(); newVertex = var.v current = var.u if !visited[newVertex] MST[current] = addEdge(MST[current], newVertex, var.weight) MST[newVertex] = addEdge(MST[newVertex], current, var.weight) current = newVertex ++i else var = PriorityQueue.extractMin(); newVertex = var.v current = var.u if !visited[newVertex] MST[current] = addEdge(MST[current], newVertex, var.weight) MST[newVertex] = addEdge(MST[newVertex], current, var.weight) current = newVertex
Or, if we put the same thing in much simpler English –
prims(InputGraph, vertices, startVertex, MST) initialise visited array to false count = 0 // counts vertices visited while count < vertices // there are vertices to visit if current node not visited mark it visited push all its edges to the PriorityQueue extract the minimum edge from PriorityQueue if the minimum edge leads to an unvisited vertex add it to MST current = newVertex ++count else extract the minimum edge from PriorityQueue again if the minimum edge leads to an unvisited vertex add it to MST current = newVertex
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.
/* * Priority Queue (Min Heap) * implementation by Arrays * for Prim's Algorithm * * Authored by, * Vamsi Sangam */ #include <stdio.h> #include <stdlib.h> struct edge { int u, v; int weight; }; void Enqueue(struct edge heap[], int size, struct edge value) { heap[size] = value; int i = size; struct edge temp; while (i >= 1) { if (heap[i / 2].weight > heap[i].weight) { //Parent node is greater than Child Node //Heap Property violated //So, swap temp = heap[i / 2]; heap[i / 2] = heap[i]; heap[i] = temp; i = i / 2; } else { //Parent is less or equal to the child //Heap property not violated //So, Insertion is done, break break; } } } void Heapify(struct edge heap[], int size, int index) { int i = index; struct edge temp; while ((2 * i) < size) { //Left Child exists if ((2 * i) + 1 >= size) { //Right child does not exist, but left does if (heap[i].weight > heap[2 * i].weight) { //Left child is smaller than parent temp = heap[i]; heap[i] = heap[2 * i]; heap[2 * i] = temp; break; //Once you reach this level where it does not //have a right child, the heap ends here //taking it to the next iteration is pointless } } //Both Children exist if (heap[i].weight > heap[2 * i].weight || heap[i].weight > heap[2 * i + 1].weight) { //One of the other child is lesser than parent //Now find the least amoung 2 children if (heap[2 * i].weight <= heap[(2 * i) + 1].weight) { //Left Child is lesser, so, swap temp = heap[2 * i]; heap[2 * i] = heap[i]; heap[i] = temp; //And go down the heap i = 2 * i; } else if (heap[2 * i].weight > heap[(2 * i) + 1].weight) { //Left Child is lesser, so, swap temp = heap[(2 * i) + 1]; heap[(2 * i) + 1] = heap[i]; heap[i] = temp; //And go down the heap i = (2 * i) + 1; } } else { //Parent is lesser than its children break; } } } void DeleteNode(struct edge heap[], int size, int index) { //Swap the indexed element with the last struct edge temp = heap[index]; heap[index] = heap[size - 1]; heap[size - 1] = temp; int i = index; --size; Heapify(heap, size, i); }
Other implementations of Prim’s Algorithm
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|2. 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…! 🙂
9 thoughts on “Prim’s Algorithm”
Would you happen to know how to do it in Python?
Will post it in the Github repo. 🙂
Hey vamshi, i tried running your code and there was a mistake.
1. In the function prim, when we find out that vertex is visited we simply extract the minimum from the heap right,now we need to increment the i value, so at line 155 there should be i++ .
Thanks for your post,i had a hard time implementing it,your post made it easier. 🙂
Nice Effort Vamsi…. Prims concepts got fully cleared through u post. Your Code is also very good….
Thanks a lot! 🙂
what will answer if input is
5 6
1 2 3
1 3 4
4 2 6
5 2 2
2 3 5
3 5 7
1
Vamsi,I request you to please give STL versions also,because many of us are not comfortable with pointers and linked list 🙂 .So,It’s my humble request if you could attach a github link with every algorithm you have published till now,having it’s Stl version also.No need to describe that fully just comments after every important line of algorithm will do.It’s my request 🙂 It would be best if you can do this ASAP 🙂 .Very nice initiative BTW
Done..! 😀 …. Check out –
Thanks to you, I learnt a couple of things about C++ today..! I will add the STL versions of other algorithms gradually… Have a nice day…!! 🙂
@CompetitiveCoder …. I have implemented a STL version of PRIMS ( both adjacency list and priority queue.
Checkout:- http://ideone.com/1mgkx2