here is only basic implementation of problems for beginners. If you have any problem with any solution or any basic concept of programming or you want more efficient solution you can mail me.
my suggestion is not to copy and paste codes from here try to understand the logic and think why you were not able to solve it.

Thursday 2 October 2014

Minimum spanning tree kruskal algorithm

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;
}

No comments:

Post a Comment