PROGRAM FOR KRUSHKALS ALGORITHM

program for krushkals algorithm
itprofessionalsrocks.blogspot.com
#include<iostream.h>
#include<conio.h>
#define infinity 1000
int num_of_nodes;
int cost[10][10];
int parent[10];
int solution[10][2];
int min_edge(int *,int *) ;
int find(int);
void unite(int,int);
void main()
{
int i=0;
int j=0;
int k=0;
int u=0;
int v=0;
int min_cost=0;
int cost_of_uv=0;
clrscr();
cout<<"\n enter the number of nodes in the graph:";
cin>>num_of_nodes;
cout<<"\nn!!!!!!enter 1000 for a not conncted link!!!\n";
for(i=0;i<num_of_nodes;i++)
{
cost[i][j]=0;
parent[i]=-1;
for(j=(i+1);j<num_of_nodes;j++)
{
cout<<"\n enter the cost from node"<<i+1<<"to node"<<j+1<<"";
cin>>cost[i][j] ;
if(cost[i][j]>=infinity)
cost[i][j]=infinity;
}

}
i=0;
while((i<num_of_nodes-1)&&(cost_of_uv!=infinity))
{
cost_of_uv=min_edge(&u,&v);
j=find(u);
k=find(v);
if(j!=k)
{
solution[i][0]=u;
solution[i][1]=v;
min_cost=min_cost+cost_of_uv;
unite(j,k);
i=i+1;
}
}
if(i!=num_of_nodes-1)
cout<<"\n no spanning trees" ;
else
{
cout<<"\n spanning tree is:";
for(i=0;i<num_of_nodes-1;i++)
cout<<"\n"<<solution[i][0]+1<<""<<solution[i][1]+1;
cout<<"\n cost of spanning tree:"<<min_cost;
}
getch();

}
int min_edge(int *x,int *y)
{
int i=0;
int j=0;
int min=1000;
int u=0;
int v=0;
for(i=0;i<num_of_nodes;i++)
{
for(j=(i+1);j<num_of_nodes;j++)
{
if((cost[i][j]!=-1))
{
if(min>cost[i][j])
{
min=cost[i][j];
u=i;
v=j;
}
}
}
}
cost[u][v]=-1;
*x=u;
*y=v;
return min;
}
int find(int i)
{
while(parent[i]>=0)
i=parent[i];
return i;
}
void unite(int i,int j)
{
parent[i]=j;
}