KRUSKAL ALGORITHM

MINIMUM SPANNING TREE

KRUSKAL ALGORITHM

#include”iostream.h”
#include”conio.h”
class kruskal
{
struct node
{
int s;
int e;
int c;
};
node a[10],b[10];
int n,p[10],r[10];
public:
int getdata();
int findset(int);
void mintree(int);
void makeset(int);
void uni(int,int);
void link(int,int);
};

int kruskal::getdata()
{
int i,j,d,cn=0;
cout<<"Enter the number of vertices\n\n";
cin>>n;
for(i=0;i {
makeset(i);
for(j=i+1;j {
if(i!=j)
{
cout<<"Enter the cost of "<<"("< cin>>d;
if(d!=0)
{
a[cn].s=i+1;
a[cn].e=j+1;
a[cn].c=d;
cn++;
}
}
}
}
for(i=0;i {
for(j=i;j {
if(a[i].c>a[j].c)
{
int temp=a[i].s;
a[i].s=a[j].s;
a[j].s=temp;

temp=a[i].e;
a[i].e=a[j].e;
a[j].e=temp;

temp=a[i].c;
a[i].c=a[j].c;
a[j].c=temp;
}
}
}
cout<<"\nStart\tEnd\tCost\n";
for(i=0;i cout<<"\n"< return(cn);
}

void kruskal::makeset(int x)
{
p[x]=x;
r[x]=0;
}

void kruskal::uni(int x,int y)
{
int a=findset(x);
int b=findset(y);
link(a,b);
}

void kruskal::link(int x,int y)
{
if(r[x]>r[y])
p[y]=x;
else
p[x]=y;
if(r[x]==r[y])
r[y]=r[y]+1;
}

int kruskal::findset(int x)
{
if(x!=p[x])
p[x]=findset(p[x]);
return(p[x]);
}

void kruskal::mintree(int a1)
{
int i,j,u,v,ctr=0;
for(i=0;i {
u=a[i].s;
v=a[i].e;
if(findset(u)!=findset(v))
{
uni(u,v);
b[ctr].s=u;
b[ctr].e=v;
b[ctr].c=a[i].c;
ctr++;
}
}
cout<<"Edges in the minimum spanning tree\n";
for(i=0;i cout<<"\nEdge:"<<"("<}

void main()
{
kruskal k;
clrscr();
int a1=k.getdata();
k.mintree(a1);
getch();
}