Minimum Spanning Tree in C++ Using Prim’s Algorithm with Priority Queue

A Minimum Spanning Tree (MST) is a subset of edges in a connected, weighted graph that connects all vertices without forming a cycle and with the minimum possible total edge weight. In this blog post, we implement Prim’s Algorithm using a min-heap (priority queue) to efficiently calculate the MST.

Minimum Spanning Tree in C++ Using Prim’s Algorithm with Priority Queue

class Solution {
  public:
    // Function to find sum of weights of edges of the Minimum Spanning Tree.
    int spanningTree(int V, vector<vector<int>> adj[]) {
        // code here
        vector<bool> vis(V,false);
        int total=0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
        q.push({0,0});
        while(!q.empty()){
            int node=q.top().second;
            int curc=q.top().first;
            q.pop();
            if(vis[node]){
                continue;
            }
            vis[node]=true;
            total+=curc;
            for(int i=0;i<adj[node].size();i++){
                int newn=adj[node][i][0];
                int newc=adj[node][i][1];
                if(!vis[newn]){
                    q.push({newc,newn});
                }
            }
        }
        return total;
    }
};

Input Format

• V: Number of vertices.

• adj: Adjacency list of the graph where adj[i] contains pairs of connected node and edge weight.

Output

• Returns the total weight of the edges included in the Minimum Spanning Tree.

Sample Input Representation

Graph:
Vertices: 4
Edges:
0 - 1 (weight 1)
0 - 2 (weight 3)
1 - 2 (weight 1)
1 - 3 (weight 4)
2 - 3 (weight 1)

Adjacency list format:
adj[0] = {{1,1}, {2,3}};
adj[1] = {{0,1}, {2,1}, {3,4}};
adj[2] = {{0,3}, {1,1}, {3,1}};
adj[3] = {{1,4}, {2,1}};

Sample Output
3