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