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

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

```/*
* Prim's Algorithm
* using a Min Heap
*
* Authored by,
* Vamsi Sangam.
*
*/

#include <cstdio>
#include <cstdlib>

using namespace std;

struct node {
int val;
int weight;
struct node * next;
};

struct edge {
int weight;
int u, v;	// edge from u ---> v
};

// Adds an edge to an Adjacency List element
struct node * addEdge(struct node * head, int num, int weight)
{
struct node * p = (struct node *) malloc(sizeof(struct node));

p->val = num;
p->weight = weight;

return p;
}

// Enqueues an entry into the Priority Queue
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) {
temp = heap[i / 2];
heap[i / 2] = heap[i];
heap[i] = temp;

i = i / 2;
} else {
break;
}
}
}

void Heapify(struct edge heap[], int size, int index)
{
int i = index;
struct edge temp;

while ((2 * i) < size) {
if ((2 * i) + 1 >= size) {
if (heap[i].weight > heap[2 * i].weight) {
temp = heap[i];
heap[i] = heap[2 * i];
heap[2 * i] = temp;

break;
}
}

if (heap[i].weight > heap[2 * i].weight || heap[i].weight > heap[2 * i + 1].weight) {
if (heap[2 * i].weight <= heap[(2 * i) + 1].weight) {
temp = heap[2 * i];
heap[2 * i] = heap[i];
heap[i] = temp;

i = 2 * i;
} else if (heap[2 * i].weight > heap[(2 * i) + 1].weight) {
temp = heap[(2 * i) + 1];
heap[(2 * i) + 1] = heap[i];
heap[i] = temp;

i = (2 * i) + 1;
}
} else {
break;
}
}
}

// Deletes and entry in the Priority Queue
void DeleteNode(struct edge heap[], int size, int index)
{
struct edge temp = heap[index];

heap[index] = heap[size - 1];
heap[size - 1] = temp;

int i = index;
--size;

Heapify(heap, size, i);
}

// Returns the element with
// Minimum Priority and deletes it
struct edge ExtractMin(struct edge heap[], int size)
{
struct edge min = heap[0];

DeleteNode(heap, size, 0);

return min;
}

// Prim's Algorithm function
void Prim(struct node * adjacencylist[], int vertices, int edges, int startVertex, struct node * MST[])
{
int current = startVertex, newVertex;
bool visited[vertices + 1];
struct node * temp;
struct edge var;
struct edge PriorityQueue[2 * edges];
int QueueSize = 0;

int i;

for (i = 0; i <= vertices; ++i) {		// Initializing
visited[i] = false;
}

i = 0;

while (i < vertices) {
if (!visited[current]) {			// If current node is not visited
visited[current] = true;		// Mark it visited

while (temp != NULL) {
var.u = current;
var.v = temp->val;
var.weight = temp->weight;

if (!visited[var.v]) {
// If the edge leads to an un-visited
// vertex only then enqueue it
Enqueue(PriorityQueue, QueueSize, var);
++QueueSize;
}

temp = temp->next;
}

var = ExtractMin(PriorityQueue, QueueSize);		// The greedy choice
--QueueSize;

newVertex = var.v;
current = var.u;

if (!visited[newVertex]) {
// If it leads to an un-visited vertex, add it to MST
MST[current] = addEdge(MST[current], newVertex, var.weight);
MST[newVertex] = addEdge(MST[newVertex], current, var.weight);
}

current = newVertex;
++i;
} else {

var = ExtractMin(PriorityQueue, QueueSize);
--QueueSize;

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;
}
}
}

int main()
{
int vertices, edges, i, j, v1, v2, weight;

printf("Enter the Number of Vertices -\n");
scanf("%d", &vertices);

printf("Enter the Number of Edges -\n");
scanf("%d", &edges);

struct node * adjacency_list[vertices + 1];
struct node * MST[vertices + 1];

for (i = 0; i <= vertices; ++i) {
MST[i] = NULL;
}

for (i = 1; i <= edges; ++i) {
scanf("%d%d%d", &v1, &v2, &weight);
}

// Printing Adjacency List
for (i = 1; i <= vertices; ++i) {
printf("adjacency_list[%d] -> ", i);

struct node * temp = adjacency_list[i];

while (temp != NULL) {
printf("%d -> ", temp->val);
temp = temp->next;
}

printf("NULL\n");
}

int startVertex;

printf("\nEnter a Start Vertex - ");
scanf("%d", &startVertex);
Prim(adjacency_list, vertices, edges, startVertex, MST);

// Printing MST
printf("\nMinimum Spanning Tree -\n\n");
for (i = 1; i <= vertices; ++i) {
printf("MST[%d] -> ", i);

struct node * temp = MST[i];

while (temp != NULL) {
printf("%d -> ", temp->val);
temp = temp->next;
}

printf("NULL\n");
}

return 0;
}
```

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…! Commenting is super easy if you are a Facebook, Twitter or a Google+ user…! So, don’t hesitate..! 😉 … Keep practising… Happy Coding…! 🙂

You may also like –

More in the Navigation Page ! →

2 thoughts on “Prim’s Algorithm”

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

Like

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

Like