Prim’s Algorithm – Minimum Spanning Tree (MST)

Arunima Mandal

Note:

It’s a greedy approach. Basically, there are 3 steps in Krushkal’s algorithm.

  1. Build an adjacency matrix
  2. Select a random node to start with and push that to the priority queue(ascending ordered value.)
  3. Do this until the number of nodes added to the MST list is less than the total number of nodes n:
    • For each top() of the priority queue, check whether the node has already been considered for the MST list, if not then do:
      • Add that node to the MST list (marked visited)
      • Add the cost(surely it will be the lowest value possible in the priority queue) of the edge to the answer
      • Push all the adjacent nodes of that node to the priority queue to determine which node to add next.

Time Complexity:

O(ElogV) where E is the number of edges and V is the number of nodes.

Code:

#include <bits/stdc++.h>

using namespace std;

int Prims(vector<vector<pair<int, int> > > &edges, int n)
{
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >pq;
    int vis[1003]= {0};
    int ans=0;
    int nodes_added=0;
    pq.push({0,0});
    while(nodes_added<n)
    {
        int cost=pq.top().first;
        int node=pq.top().second;
        pq.pop();
        if(!vis[node])
        {
            nodes_added++;
            vis[node]=1; //added to MST
            ans+=cost;
            for(int i=0; i<edges[node].size(); i++)
            {
                pq.push(edges[node][i]);
            }
        }
    }
    return ans;
}

int main()
{
    int n,m;
    cout<<"Enter the no. of nodes in the graph: ";
    cin>>n;
    cout<<"Enter the no. of edges: ";
    cin>>m;
    vector<vector<pair<int, int> > > edges(n);
    cout<<"Enter the and their corresponding cost (node node cost):"<<endl;
    for(int i=0; i<m; i++) //Building adjacency graph
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        edges[x].push_back({cost, y});
        edges[y].push_back({cost, x});
    }
    int ans=Prims(edges, n);
    cout<<"The minimum cost for traversing all the nodes once: "<<ans<<endl;
    return 0;
}
/*
Sample input:
5
7
0 1 1
0 2 2
0 3 3
1 2 2
2 3 3
3 4 4
4 0 5

Sample Output:
10

Note: Minimum spanning tree formed by nodes 0-1-2-3-4

*/

Leave a comment