Prim’s Algorithm using C++ STL

Hello people..! This is a special extension to my post on Prim’s Algorithm. Here, I give you a different implementation of Prim’s Algorithm which uses C++ STL. So, those who are uncomfortable with using pointers should feel just at home with this…! Provided you know C++ STL..! 😉 … Some of the features of this code are –

• The Adjacency List used is exactly as in Adjacency List using C++ STL
• The Min Heap is unchanged from the former post on Prim’s Algorithm. We stick to the array of structs.
• The Prim’s algorithm function uses C++ reference parameters to yield the necessary results.
```/*
* Prim's Algorithm for
* Undirected Weighted Graph
* Code using C++ STL
*
* Authored by,
* Vamsi Sangam.
*
*/

#include <cstdio>
#include <vector>
#include <list>
#include <utility>

using namespace std;

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

// 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(
vector< list< pair<int, int> > > & adjacencyList,
int vertices,
int edges,
int startVertex,
vector< list< pair<int, int> > > & MST
)
{
int current = startVertex, newVertex;
bool visited[vertices + 1];
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

list< pair<int, int> >::iterator itr = adjacencyList[current].begin();

if (!visited[(*itr).first]) {
// If the edge leads to an un-visited
// vertex only then enqueue it
var.u = current;
var.v = (*itr).first;
var.weight = (*itr).second;

Enqueue(PriorityQueue, QueueSize, var);
++QueueSize;
}

++itr;
}

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

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

if (!visited[newVertex]) {
MST[current].push_back(make_pair(newVertex, var.weight));
MST[newVertex].push_back(make_pair(current, var.weight));
}

current = newVertex;
++i;
} else {

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

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

if (!visited[newVertex]) {
MST[current].push_back(make_pair(newVertex, var.weight));
MST[newVertex].push_back(make_pair(current, var.weight));
}

current = newVertex;
}
}
}

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

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

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

// Adjacency List is a vector of list.
// Where each element is a pair<int, int>
// pair.first -> the edge's destination
// pair.second -> edge's weight
vector< list< pair<int, int> > > adjacencyList(vertices + 1);
vector< list< pair<int, int> > > MST(vertices + 1);

printf("Enter the Edges V1 -> V2, of weight W\n");

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

// Adding Edge to the Directed Graph
}

for (int i = 1; i < adjacencyList.size(); ++i) {

list< pair<int, int> >::iterator itr = adjacencyList[i].begin();

printf(" -> %d(%d)", (*itr).first, (*itr).second);
++itr;
}
printf("\n");
}

int startVertex;

printf("\nEnter a Start Vertex - ");
scanf("%d", &startVertex);

printf("\nThe Minimum Spanning Tree-\n");
for (int i = 1; i < MST.size(); ++i) {
printf("MST[%d] ", i);

list< pair<int, int> >::iterator itr = MST[i].begin();

while (itr != MST[i].end()) {
printf(" -> %d(%d)", (*itr).first, (*itr).second);
++itr;
}
printf("\n");
}

return 0;
}
```

Keep comparing every strange line with the simple C code… I’m sure you’ll get it..! 🙂 … Feel free to comment if you have any doubts..! Keep practising..! Happy Coding..! 😀

7 thoughts on “Prim’s Algorithm using C++ STL”

1. Dan says:

Sadly, your code (which you updated using STL objects like list and which I found at your GitHub repo) emits compilation errors from a modern compiler. Modern C++ (evidently) prohibits variable length arrays of non-POD types (“plain old data”). The hangup is going to be passing indexable (by vertex) arrays of adjacency lists to the algorithm. Also, your Prim algorithm seems to be full of twists and turns. Of course, not to you, who (I trust) wrote it.

2. Dan says:

Sorry for the first (somewhat curt) reply. I found your Github repo with updated code, and it has no errors, so far. I’m interested in modifying it so I don’t have to use integer weights, and will get back to you if I have problems.

3. Dan says:

The above code segfaults on a simple tree, searching from 1, tree: 1-2 1-3 1-4 1-5 1-6; gcc 6.4.0. This graph is connected, is it not?
The bad access occurs in ExtractMin() when we try to return min uninitialized.

4. Deepak Dodeja says:

Can you please tell how to make prims algorithm with the use of bfs and priority queue in c++.

1. Hi, Deepak…! I don’t think you can make Prim’s Algorithm with BFS.. Because BFS is meant for unweighted graphs… If you do find a way to do it please share it here in the comments 🙂

1. Maulik Solanki says:

Can you please implement using priority que stl in c++.