/* Program to implement Kruskal's Algorithm */
#include<stdio.h>
#include<stdlib.h>
void makeset();
void graph(int);
void kruskal();
struct node *findset(struct node *);
void union1(struct node *,struct node *);
int j=0;
struct node //Declare the structure of a node
{
int data,rank;
struct node *next,*parent;
};
struct edge //Declare the structure of a edge
{
int len;
struct node *src,*destination;
};
struct node *head[10];
struct edge *e[40];
int main()
{
int n,i;
printf("\nEnter no.of vertices in the graph : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
makeset(i); //initialise each vertex
}
graph(n);
kruskal();
}
void makeset(int a)
{
struct node *x;
x=(struct node*)malloc(sizeof(struct node));
x->data=a;
x->parent=x;
x->rank=0;
x->next=NULL;
head[a]=x;
}
void graph(int n) //here input neighbours of each vertex & the weight of edges
{
int i,k,l,len;
int dest;
for(i=1;i<=n;i++)
{
printf("\nfor vertex %d Enter no. of edges ",i);
scanf("%d",&l);
for(k=1;k<=l;k++)
{
printf("Enter destination vertex for %dth edge for vertex %d ",k,i);
scanf("%d",&dest);
j++;
e[j]=(struct edge*)malloc(sizeof(struct edge));
e[j]->src=head[i];
e[j]->destination=head[dest];
printf("Enter length of edge : ");
scanf("%d",&len);
e[j]->len=len;
}
}
}
void kruskal() //Apply actual concept of kruskal
{
int i,k,l,p;
struct edge *temp;
i=1;
while(i<j) //sort the edges with increasing order of their weights
{ //using insertion sort
p=i;
k=i+1;
while(k<=j)
{
if(e[p]->len>e[k]->len)
{
p=k;
}
k++;
}
if(p!=i)
{
temp=e[p];
e[p]=e[i];
e[i]=temp;
}
i++;
}
printf("\nMST includes the following edges that are :\n");
for(i=1;i<=j;i++)
{
if(findset(e[i]->src)!=findset(e[i]->destination)) //if representative
{ //of src & dest. are different
union1((findset(e[i]->src)),(findset(e[i]->destination))); //then make connection
printf("\n%d->%d",e[i]->src->data,e[i]->destination->data); //b/w them
}
}
}
struct node *findset(struct node *a) //return the represenative of node
{
if(a!=a->parent)
{
a->parent=findset(a->parent);
}
return a->parent;
}
void union1(struct node *x,struct node *y) //join the two vertex if desired
{
if(x->rank>y->rank)
y->parent=x;
else
x->parent=y;
if(x->rank==y->rank)
y->rank=y->rank+1;
}
