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..! Keep practising..! Happy Coding..! 😀

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

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

Leave a Reply to Deepak Dodeja Cancel reply