Same as the Kruskal's algorithm, this algorithm finds the minimum spanning tree in a graph.
The difference is that Prim's algorithm works faster in case of dense graphs while Kruskal's algorithm works well in sparse graphs.
Both have the same time complexity O(ElogV).
The implementation is the same as that of Djikstra's algorithm. The only difference is that
for a node(which is visited first), the distance of its child is the distance from that node to its child but not from the source node.
And I am using a disjoint set to have the minimum-spanning-tree.
Source Code:
Output:
The difference is that Prim's algorithm works faster in case of dense graphs while Kruskal's algorithm works well in sparse graphs.
Both have the same time complexity O(ElogV).
The implementation is the same as that of Djikstra's algorithm. The only difference is that
for a node(which is visited first), the distance of its child is the distance from that node to its child but not from the source node.
And I am using a disjoint set to have the minimum-spanning-tree.
Source Code:
///for undirected graph....
#include<bits/stdc++.h>
using namespace std;
template<class T>
class Graph{
unordered_map< T, vector< pair<T,int> > >g;
unordered_map<T,int>distance;
set<pair<int,T>>dist_min_set;
vector<bool>mark;
int disjoint_set[1000];
public:
void insert_node(T u,T v,int weight){
g[u].push_back( make_pair(v,weight) );
g[v].push_back( make_pair(u,weight) );
}
void display(){
for(auto i : g){
cout << i.first <<"--> ";
for(auto it : i.second){
cout <<"("<< it.first << " , "<<it.second<<" ), ";
}
cout << "\n";
}
}
void prim(T source,int n){
for(int i = 0 ; i < n ; i++){
disjoint_set[i] = i;
}
for(int i=0;i<n;i++)
mark.push_back(false);
for(auto i:g){
distance[i.first] = 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());
T parent = p->second;
mark[parent] = true;
for(auto it = g[parent].begin(); it != g[parent].end(); it++){
T 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,weight;
cout << "Enter the number of vertices:";
cin >> n;
cout << "Enter the number of edges";
cin >> m;
Graph<int>g;
int u,v;
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();
g.prim(0,n,m);
}
Output:
Enter the number of vertices:4
Enter the number of edges5
Enter u,v and weight 0 1 10
Enter u,v and weight 0 2 6
Enter u,v and weight 3 2 4
Enter u,v and weight 1 0 5
Enter u,v and weight 1 3 15
3--> (2 , 4 ), (1 , 15 ),
2--> (0 , 6 ), (3 , 4 ),
1--> (0 , 10 ), (0 , 5 ), (3 , 15 ),
0--> (1 , 10 ), (2 , 6 ), (1 , 5 ),
The minimum spanning tree is
Weight of (0 , 1) is 5
Weight of (0 , 2) is 6
Weight of (2 , 3) is 4
Comments
Post a Comment