Minimum spanning tree (MST) is a subset of the edges of a undirected/directed weighted graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
A single graph can have many different spanning trees.
In other words,
A minimum spanning tree (MST) is a spanning tree with weight less than or equal to the weight of every other spanning tree.
To eliminate cycles from the graph to build MST, we use disjoint-set datastructure.
Resources I used to learn this algorithm:
1. For kruskal algorithm ,
2. For disjoint set ,
3. Implementation of the kruskal algorithm.
Here is my source code:
Output:
A single graph can have many different spanning trees.
In other words,
A minimum spanning tree (MST) is a spanning tree with weight less than or equal to the weight of every other spanning tree.
To eliminate cycles from the graph to build MST, we use disjoint-set datastructure.
Resources I used to learn this algorithm:
1. For kruskal algorithm ,
2. For disjoint set ,
3. Implementation of the kruskal algorithm.
Here is my source code:
#include<bits/stdc++.h>
using namespace std;
class Graph{
vector < pair< int, pair<int , int> > >g;
int disjoint_set[1000],n,m;
public:
Graph(int n,int m){
this -> n = n;
this -> m = m;
for(int i = 0 ; i < this -> n ; i++){
disjoint_set[i] = i;
}
}
void insert_node(int u,int v,int weight){
g.push_back(make_pair(weight,make_pair(u,v)));
}
void display(){
for(auto it = g.begin(); it != g.end() ; it++){
cout<<it->second.first<<", "<<it->second.second<<" and weight is "<<it->first;
cout << "\n";
}
}
int find_set(int s){
if(disjoint_set[s] == s){
return s;
}
disjoint_set[s] = find_set(disjoint_set[s]);
return disjoint_set[s];
}
void union_set(int x,int y){
int u = find_set(x);
int v = find_set(y);
disjoint_set[v] = u;
}
void krushkal(){
sort(g.begin(),g.end());
int mst_edges = 0;
for(auto it = g.begin(); it != g.end() ; it++){
if(mst_edges == n-1){
break;
}
int weight = it -> first;
int u = it -> second.first;
int v = it -> second.second;
if(find_set(u) != find_set(v)){
union_set(u,v);
cout<<"Weight of "<<"( "<<u<<", "<<v<<" )"<<" is "<<weight<<"\n";
mst_edges++;
}
}
}
};
int main(){
int n,m,weight;
cout << "Enter the number of vertices:";
cin >> n;
cout << "Enter the number of edges";
cin >> m;
Graph g(n,m);
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();
cout << "\nThe minimum Spanning Tree is \n";
g.krushkal();
}
Output:
Enter the number of vertices:4
Enter the number of edges5
Enter u,v and weight0 1 10
Enter u,v and weight1 3 5
Enter u,v and weight0 2 6
Enter u,v and weight2 3 4
Enter u,v and weight0 3 5
Weight of ( 0, 1 ) is 10
Weight of ( 1, 3 ) is 5
Weight of ( 0, 2 ) is 6
Weight of ( 2, 3 ) is 4
Weight of ( 0, 3 ) is 5
The minimum Spanning Tree is
Weight of ( 2, 3 ) is 4
Weight of ( 0, 3 ) is 5
Weight of ( 1, 3 ) is 5
Comments
Post a Comment