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 whereadj[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