PrimsAlgorithm.cpp

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
using namespace std;

int main()
{
 int N;
 cout<<"Enter the number of vertices :-";
 cin>>N;

 vector<pair<int,int> > G[N+1];
 int M;

 cout<<"Enter the number of edges :-";
 cin>>M;

 cout<<"Enter two vertices for which an edge exists between them :-\n";

 for(int i=0;i<M;i++)
 {
 int U,V,W;
 cin>>U>>V>>W;
 G[U].push_back(make_pair(V,W));
 G[V].push_back(make_pair(U,W));
 }

 int S;
 cout<<"Enter the source node :-";
 cin>>S;

 set<pair<int,int> > PQ;

 vector<int> parent(N+1,-1);
 vector<int> dist(N+1,123456789);
 vector<bool> visited(N+1,false);

 dist[S]=0;

 for(int i=1;i<=N;i++)
 {
 PQ.insert(make_pair(dist[i],i));
 }
 vector<pair<int,int> > MST_edges;
 int total_cost=0;
 while(!PQ.empty())
 {
 pair<int,int> H=*PQ.begin();
 PQ.erase(PQ.begin());
 visited[H.second]=true;

 if(H.second!=S)
 {
 MST_edges.push_back(make_pair(parent[H.second],H.second));
 }

 for(int i=0;i<G[H.second].size();i++)
 {
 if(visited[G[H.second][i].first]==false)
 {
 if(dist[G[H.second][i].first]>G[H.second][i].second)
 {
 PQ.erase(PQ.find(make_pair(dist[G[H.second][i].first],G[H.second][i].first)));
 dist[G[H.second][i].first]=G[H.second][i].second;
 PQ.insert(make_pair(dist[G[H.second][i].first],G[H.second][i].first));
 parent[G[H.second][i].first]=H.second;
 }
 }
 }
 }

 cout<<"The edge set of MST formed using Prims Algorithm is :-\n";

 for(int i=0;i<MST_edges.size();i++)
 {
 cout<<MST_edges[i].first<<" "<<MST_edges[i].second<<endl;
 }

 for(int i=1;i<=N;i++)
 {
 if(dist[i]!=123456789)
 {
 total_cost+=dist[i];
 }
 }
 cout<<"Total cost of constructing MST using Prims Algorithm is :- "<<total_cost<<endl;
 return 0;
}