Source Code:
///for undirected graph....
#include<bits/stdc++.h>
using namespace std;
class Graph{
int n,m;
vector< pair<int,int> >*g;
map<int,int>distance;///distance from the source node...
set<pair<int,int>>dist_min_set;
vector<bool>mark;
int disjoint_set[1000];
public:
Graph(int n,int m){
g = new vector< pair<int,int> >[n+1];
this -> n = n;
this -> m = m;
}
void insert_node(int u,int v,int weight){
g[u].push_back( make_pair(v,weight) );
g[v].push_back( make_pair(u,weight) );
}
void display(){
for(int i=0;i<n; i++){
if(g[i].size()){
cout << i << "--> ";
for(auto it = g[i].begin();it != g[i].end();it++){
cout <<"("<< it ->first << " , "<<it->second<<" ), ";
}
cout << "\n";
}
}
}
void prim(int source){
for(int i=0;i<n;i++){
disjoint_set[i] = i;
mark.push_back(false);
}
for(int i=0;i<n;i++){
distance[i]=INT_MAX;
}
distance[source] = 0;
dist_min_set.insert(make_pair(0,source));
while(!dist_min_set.empty()){
auto p = dist_min_set.begin();
dist_min_set.erase(dist_min_set.begin());
int parent = p->second;
mark[parent] = true;
for(auto it = g[parent].begin(); it != g[parent].end(); it++){
int child = it -> first;
int weight = it ->second;
if(distance[child] > weight && mark[child]==false){
if(distance[child] != INT_MAX){
dist_min_set.erase(dist_min_set.find(make_pair(distance[child],child)));
}
distance[child] = weight;
disjoint_set[child] = parent;
dist_min_set.insert(make_pair(distance[child],child));
}
}
}
cout <<"\nThe minimum spanning tree is \n";
for(auto it:distance){
if(disjoint_set[it.first] != it.first)
cout <<"Weight of "<<"("<<disjoint_set[it.first]<<" , "<<it.first<<") "<<"is "<<it.second;
cout << "\n";
}
}
};
int main(){
int n,m,u,v,weight;
cout << "Enter the number of vertices:";
cin >> n;
cout << "Enter the number of edges";
cin >> m;
Graph g(n,m);
for(int i = 0;i < m;i++){
cout << "Enter u,v and weight";
cin >> u >> v >> weight;
g.insert_node(u,v,weight);
cout << "\n";
}
g.display();
int source = 0;
g.prim(source);
}
Comments
Post a Comment