Graph Theory

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 –

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 –

Prim's Algorithm Step-by-Step
Prim’s Algorithm Step-by-Step

 

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…!

CJava
Link to code – GitHub
Link to code – GitHub

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

  1. 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. 🙂

  2. 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

Leave a Reply