Kruskal's Algorithm

//program to illustrate Kruskal's Algorithm

#include
#include
#include

struct graph
{
int u,v,wt,select;
};

class kruskal
{
graph x[30];
int n1,n2,rootn1,rootn2,mincost;
int w,k,n,c,i,j;
int father[10];

public:
kruskal()
{
k=1;
c=0;
}
void read();
void sort();
void display();
};

void kruskal::read()
{
cout<<"\n\t\tEnter the number nodes:";
cin>>n;
cout<<"\n\t\tEnter the weights\n";
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
cout<<"\t\t\t\t"<"< cin>>w;
if(w>0)
{
x[k].u=i;
x[k].v=j;
x[k].select=0;
x[k].wt=w;
k++;
}
}
}
sort();
}

void kruskal::sort()
{
struct graph temp;
int i,j;
for(i=1;i<=k;i++)
{
for(j=1;j<=k;j++)
{
if(x[j].wt>x[j+1].wt)
{
temp=x[j];
x[j]=x[j+1];
x[j+1]=temp;
}
}
}
}

void kruskal::display()
{
cout<<"\n\t\tMinimal spanning tree is: ";
for(i=1;i<=k;i++)
{
if(c==n)
break;
n1=x[i].u;
n2=x[i].v;
while(n1>0||n2>0)
{
if(n1>0)
{
rootn1=n1;
n1=father[n1];
}
else
{
rootn2=n2;
n2=father[n2];
}
}
if(rootn1!=rootn2)
{
father[rootn2]=rootn1;
x[i].select=1;
cout<<"\n\t\t\t"<"< mincost+=x[i].wt;
c++;
}
}
cout<<"\n\t\tMinimum cost= "<< mincost;
}

void main()
{
kruskal k;

k.read();
k.display();
getch();
}



OUTPUT

Enter the number nodes:4

Enter the weights
1->2= 2
1->3= 3
1->4= 1
2->3= 2
2->4= 5
3->4= 6

Minimal spanning tree is:
1->4=1
1->2=2
2->3=2
Minimum cost= 5