Code:-
#include<bits/stdc++.h>
using namespace std;
struct edge
{
int a,b,w;
// w = weight of edge
// edge b/w a and b
};
edge arr[1000000];
int parent[10001];
// function for compare weight of two edge
// and return true are FALSE
// on the basis of the this returned value\
// sort function work
bool cmp(edge a,edge b)
{
if(a.w<b.w)
return true;
return false;
}
// function for find the parent of the node
int find(int a)
{
if(parent[a]==-1)
return a;
return find(parent[a]);
}
// function for merge two nodes
// i.e create a edge between them
void merge(int a,int b)
{
parent[a]=b;
}
//Driver function
int main()
{
int a,b,sum=0;
int n,m;
cout<<"Enter number of nodes and number of edges\n";
cin>>n>>m;
// initialize parent arr with -1;
for(int i=1;i<=n;i++)
parent[i]=-1;
// take input all the edges
cout<<"Enter the edges\n";
for(int i=0;i<m;i++)
{
cin>>arr[i].a>>arr[i].b>>arr[i].w;
}
// sort all the edges in increassing order
// here cmp is a function which is define above
sort(arr,arr+m,cmp);
cout<<"Edges of the spanning tree are: \n";
for(int i=0;i<m;i++)
{
a=find(arr[i].a);
b=find(arr[i].b);
// if parents of the nodes are not same
// i.e it does not create cycle
// cycle is not allowed in spanning tree
if(a!=b)
{
sum=sum+arr[i].w;
cout<<a<<" to "<<b<<endl;
merge(a,b);
}
}
cout<<"Minimum weight of spanning tree : "<<sum;
return 0;
}
Output:-
Enter number of nodes and number of edges
6 10
Enter the edges
1 2 4
1 6 5
1 4 8
1 3 2
2 4 3
2 3 4
2 5 2
3 5 3
4 5 1
4 6 1
Edges of the spanning tree are :
4 to 5
5 to 6
1 to 3
2 to 6
3 to 6
Minimum weight of the spanning tree : 9
0 Comments