int prim(int source){ pq.push(make_pair(0, source)); // (weight, cost) // we have to negate as cpp has max-PQ and we need min-PQ int total_cost=0; // the total cost while(!pq.empty()){ auto pair_=pq.top(); pq.pop(); int node = pair_.second; int cost=-pair_.first; // - - = +
// now we visit all the child nodes of the current node for(auto &children:graph[node]){ if(visited[children.first]) continue; pq.push(make_pair(-children.second,children.first)); // we negate as we need min-PQ // here children.second comes first } } return total_cost; }
int main() { cin >> vertex >> edge; f(i,edge){ int to,from,weight; cin>>to>>from>>weight; graph[to].emplace_back(make_pair(from, weight)); graph[from].emplace_back(make_pair(to,weight)); } int source;cin>>source; // if source is given // cout << "MST is " << prim(source) << "\n"; cout << prim(source) << "\n"; return 0; }
Data Structure & Algorithms (Bangla Tutorials) in C++ & JAVA Graph Theory Algorithms (Bangla Tutorials) in C++/JAVA Subscribe to my YouTube channel Sayef Reyadh - Programming Made Simple
Download Link : emu8086v408r11 (With Key) Youtube Tutorial Link : Assembly Programming Tutorial in Bangla emu8086 Subscribe to my YouTube channel Sayef Reyadh - Programming Made Simple
/* created by */
ReplyDelete#include
using namespace std;
#define f(i,n) for(int i=0;i > > graph;
priority_queue< pair > pq;
bool visited[NODES]={false};
int vertex, edge;
int prim(int source){
pq.push(make_pair(0, source)); // (weight, cost) // we have to negate as cpp has max-PQ and we need min-PQ
int total_cost=0; // the total cost
while(!pq.empty()){
auto pair_=pq.top(); pq.pop();
int node = pair_.second; int cost=-pair_.first; // - - = +
if(visited[node])
continue;
visited[node]=true;
total_cost+=cost;
// now we visit all the child nodes of the current node
for(auto &children:graph[node]){
if(visited[children.first])
continue;
pq.push(make_pair(-children.second,children.first)); // we negate as we need min-PQ // here children.second comes first
}
}
return total_cost;
}
int main()
{
cin >> vertex >> edge;
f(i,edge){
int to,from,weight; cin>>to>>from>>weight;
graph[to].emplace_back(make_pair(from, weight));
graph[from].emplace_back(make_pair(to,weight));
}
int source;cin>>source; // if source is given
// cout << "MST is " << prim(source) << "\n";
cout << prim(source) << "\n";
return 0;
}