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();
            
            while (itr != adjacencyList[current].end()) {                
				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
		adjacencyList[v1].push_back(make_pair(v2, weight));
		adjacencyList[v2].push_back(make_pair(v1, weight));
	}
	
	printf("\nThe Adjacency List-\n");
	// Printing Adjacency List
	for (int i = 1; i < adjacencyList.size(); ++i) {
		printf("adjacencyList[%d] ", i);
		
		list< pair<int, int> >::iterator itr = adjacencyList[i].begin();
		
		while (itr != adjacencyList[i].end()) {
			printf(" -> %d(%d)", (*itr).first, (*itr).second);
			++itr;
		}
		printf("\n");
	}
 
    int startVertex;
 
    printf("\nEnter a Start Vertex - ");
    scanf("%d", &startVertex);
    Prim(adjacencyList, vertices, edges, startVertex, MST);
 
    printf("\nThe Minimum Spanning Tree-\n");
	// Printing Adjacency List
	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..! 😀