Prim’s MST for Adjacency List Representation in C++

In this tutorial, we will learn about the implementation of Prim’s MST for Adjacency List Representation in C++. MST stands for a minimum spanning tree. We need to calculate the minimum cost of traversing the graph given that we need to visit each node exactly once. We represent the graph by using the adjacency list instead of using the matrix. This reduces the overall time complexity of the process. We follow a greedy approach, wherein we prioritize the edge with the minimum weight.

In the standard template library available in c++, we have a data structure called priority queue which functions in a similar manner to the heaps. We enter all the edges along with their weights in the priority queue so that we always extract the edge with the minimum weight.

Given an undirected graph, we choose a node as the source node. We enter the neighboring edges of the node in the priority queue(min-heap) and extract the one with the minimum weight. As we go on selecting the nodes, we keep on adding the edges connecting those nodes in the priority queue. This ensures that every time the selected edge has the minimum weight.

Say, we have a graph given as:

Prim’s MST for Adjacency List Representation in C++

The detailed code below will show how to get the minimum spanning tree using prim’s algorithm.

Prim’s MST for Adjacency List Representation in C++ solution

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

vector<pair<int, int> >  adj_list[7];  
//to make the graph
vector<bool> visited(7,false);  
// to keep a track if the node has been already visited or not. Initially all are false as no node is visited
vector<int> connection(7,-1);  
// to track the final connections that the MST has
vector<int> value(7, INT_MAX); 
// to store the minimum weight value possible for a node
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que; 
//priority queue to extract minimum weights 

void prims() {
    que.push(make_pair(0, 1));  //push the weight required to insert the source node =0 and the node itself(i.e 1)
    value[1]=0;                 //minimum weight for source is 0  
    while (!que.empty()) {      
        int node = que.top().second;  //get the node
        visited[node] = true;         //as it is visited now change its value to true
        que.pop();                    
        for (auto neighbor : adj_list[node]) {   //we check for all its neighbors
            int weight = neighbor.second;        //get their weight
            int vertex = neighbor.first;         //get their index

            if (!visited[vertex] && value[vertex] > weight) {   //if the node is not visited and if its weight along this edge is less than the 
                value[vertex] = weight;                         //previous edge associated with it, then only we consider it
                connection[vertex] = node;
                que.push(make_pair(value[vertex], vertex));     //we update the values and then push it in the queue to examine its neighbors
            }
        }
    }
}

void print_graph() {
    for (int i = 2; i < 7; ++i)
        printf("%d - %d\n", connection[i], i);  //print the connections
}

void makegraph(int m, int n, int wght) {

    /* This function adds the edges and nodes to
      the graph in the form of an adjacency list */
    adj_list[m].push_back(make_pair(n, wght));     //make a pair of the node and its weight
    adj_list[n].push_back(make_pair(m, wght));     //we need to add it both ways i.e if a connects b, then b also connects a
}

int main() {
    makegraph(5, 4, 5);   //insert the node and edge
    makegraph(5, 1, 3);   //insert the node and edge
    makegraph(1, 2, 3);   //insert the node and edge
    makegraph(1, 4, 7);   //insert the node and edge
    makegraph(2, 5, 11);  //insert the node and edge
    makegraph(6, 4, 1);   //insert the node and edge
    makegraph(5, 6, 7);   //insert the node and edge
    makegraph(3, 1, 3);   //insert the node and edge
    makegraph(3, 2, 7);   //insert the node and edge

    prims();              //call the function the perform the minimum spanning tree algorithm
    print_graph();        //print the final minimum spanning tree

    return 0;
}

VARIABLE EXPLANATION:

Note that all the identifiers are global so that we can freely use them in every function if required.
Firstly, let us understand all the variables and their purpose.

  • We make a vector of pairs(adj_lis)  to represent the graph. The pairs are basically the edges of the graph or in other words, the connections. For example, if our graph contains an edge connecting 3 and 4, then the vector will have <3,4> and <4,3>.
  • The next variable is the vector visited which is used to mark the presence of a vertex in the MST. As we need to take each edge only once, we use this array to make sure that no vertex is visited twice or more. If the index corresponding to a vertex is marked true, then we do not visit it again.
  • The connections vector stores the final connections of the MST. For simplicity, we have assumed that 7 vertices are present and we represent each vertex as the index of the array. The indexes are used to store the vertex numbers with which they are connected. For example, connection[3]=1 means 3 is connected to 1.
  • The value vector stores the minimum weight with which we can join a vertex.
  • The priority queue is used to extract edges with minimum weight at every step.

CODE EXPLANATION

  1. Let us start understanding from the main() function. Firstly, we make a graph using the make graph() function which takes in the connections as its parameters and keeps on adding the edges in the graph. The final result is a graph that is represented in the form of an adjacency list.
    void makegraph(int m, int n, int wght) { 
    /* This function adds the edges and nodes to 
    the graph in the form of an adjacency list */ 
    
    adj_list[m].push_back(make_pair(n, wght)); 
    //make a pair of the node and its weight 
    
    adj_list[n].push_back(make_pair(m, wght));
    //we need to add it both ways i.e if a connects b, then b also connects a 
    }
  2. Next, the main function calls the prims() function which gives us our MST.
  3. We are using a min-heap in the form of a priority queue so that we can extract the minimum weight possible at every step.
  4. Firstly, we add the source vertex to the queue along with its weight(0) and update its value vector to 0.
    que.push(make_pair(0, 1)); 
    value[1]=0;
  5. Then, we keep on repeating the following process until we get our MST:
    At each step, we consider the top element of the(because it has the minimum weight) and mark it as visited.

    int node = que.top().second; 
    visited[node] = true; 
    que.pop()

    We check all its neighbors and if they are not already visited and their value is less than that possible with some other edge, we push them to the queue.

    for (auto neighbor : adj_list[node]) { 
    int weight = neighbor.second;
    int vertex = neighbor.first; 
        if (!visited[vertex] && value[vertex] > weight) { 
            value[vertex] = weight; 
            connection[vertex] = node; 
            que.push(make_pair(value[vertex], vertex)); 
        }
  6. Finally, we print the MST using the print_graph() function.

We get the output as :

1 - 2
1 - 3
5 - 4
1 - 5
4 - 6

Time complexity: ElogV (E: no of edges, V: number of nodes)

To read more:

Adjacency List in C++

Minimum Spanning Tree for Graph in C++

Leave a Reply

Your email address will not be published. Required fields are marked *