Time complexity O(eLoge + eLogv)
steps:-
sort all the edges according to their weights
pick minimum weighted edge and check for cycle
if(makes cycle) -> discard that edge
else -> take it
repeat it until we get v-1 nodes
no of edges in final tree = v-1
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int e,v;
struct nodes{
int a;
int b;
int w;
};
struct checker{
int parent;
int rank;
};
bool compare (nodes p1, nodes p2){
return (p1.w > p2.w);
}
int find( struct checker br[], int i){
if (br[i].parent != i){
br[i].parent = find(br, br[i].parent);
}
return br[i].parent;
}
void Union(struct checker br[],int x,int y){
int xroot = find(br, x);
int yroot = find(br, y);
if (br[xroot].rank < br[yroot].rank){
br[xroot].parent = yroot;
}else if (br[xroot].rank > br[yroot].rank){
br[yroot].parent = xroot;
}else{
br[yroot].parent = xroot;
br[xroot].rank++;
}
}
int kruskal(vector<nodes>& ar){
int weight=0;
struct checker br[1000];
int i;
sort(ar.begin(),ar.end(),compare);
for(i=0;i<v;i++){
br[i].parent=i;
br[i].rank=0;
}
int z=0;
for(i=e-1;i>=0;i--){
int x=find(br,ar[i].a);
int y=find(br,ar[i].b);
if(x!=y){
Union(br,ar[i].a,ar[i].b);
weight+=ar[i].w;
z++;
}
if(z==v-1){
break;
}
}
return weight;
}
int main(){
int c,d,r,i,j,n,m;
vector<nodes> ar(1000);
printf("Enter no of vertexes and edges\n");
scanf("%d %d",&v,&e);
printf("Edges\n");
for(i=0;i<e;i++){
scanf("%d %d %d",&ar[i].a,&ar[i].b,&ar[i].w);
}
c=kruskal(ar);
printf("%d\n",c);
return 0;
}
steps:-
sort all the edges according to their weights
pick minimum weighted edge and check for cycle
if(makes cycle) -> discard that edge
else -> take it
repeat it until we get v-1 nodes
no of edges in final tree = v-1
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int e,v;
struct nodes{
int a;
int b;
int w;
};
struct checker{
int parent;
int rank;
};
bool compare (nodes p1, nodes p2){
return (p1.w > p2.w);
}
int find( struct checker br[], int i){
if (br[i].parent != i){
br[i].parent = find(br, br[i].parent);
}
return br[i].parent;
}
void Union(struct checker br[],int x,int y){
int xroot = find(br, x);
int yroot = find(br, y);
if (br[xroot].rank < br[yroot].rank){
br[xroot].parent = yroot;
}else if (br[xroot].rank > br[yroot].rank){
br[yroot].parent = xroot;
}else{
br[yroot].parent = xroot;
br[xroot].rank++;
}
}
int kruskal(vector<nodes>& ar){
int weight=0;
struct checker br[1000];
int i;
sort(ar.begin(),ar.end(),compare);
for(i=0;i<v;i++){
br[i].parent=i;
br[i].rank=0;
}
int z=0;
for(i=e-1;i>=0;i--){
int x=find(br,ar[i].a);
int y=find(br,ar[i].b);
if(x!=y){
Union(br,ar[i].a,ar[i].b);
weight+=ar[i].w;
z++;
}
if(z==v-1){
break;
}
}
return weight;
}
int main(){
int c,d,r,i,j,n,m;
vector<nodes> ar(1000);
printf("Enter no of vertexes and edges\n");
scanf("%d %d",&v,&e);
printf("Edges\n");
for(i=0;i<e;i++){
scanf("%d %d %d",&ar[i].a,&ar[i].b,&ar[i].w);
}
c=kruskal(ar);
printf("%d\n",c);
return 0;
}
No comments:
Post a Comment