6.12 Kruskal Algorithm

#include
#include
#include
#include
#define max(a,b)(a>b?a:b)
class ll_node
{
public:
int src,dest,weight;
ll_node *next;
};
int *parent;
char err[]="Some nodes in the tree are isolated";
void error(char *msg)
{
puts(msg);
exit(1);
}
void put_sorted(ll_node *phead,ll_node *node)
{
ll_node *cur,*prev;
prev=phead;
cur=phead->next;
while(cur && cur->weightweight)
{
prev=cur;
cur=cur->next;
}
node->next=cur;
prev->next=node;
}
int input(ll_node *phead)
{
char c;
int p=0;
int i,j,n=0,w;
ll_node *node;
char inps[80];

do
{
p=1;
cout<<"Input the edges as : ";
cout< gets(inps);
while(sscanf(inps,"%d %d %d",&i,&j,&w)==3)
{
cout< node=new ll_node;
node->src=i-1;
node->dest=j-1;
node->weight=w;
n=max(n,i);
n=max(n,j);
put_sorted(phead,node);
gets(inps);
}
puts(inps);
}while(!p);
return(n);
}
int root(int *parent,int node)
{
while(parent[node]!=node)
node=parent[node];
return node;
}
int min_span(ll_node *phead,int n)
{
ll_node *first,*cur,*temp;
int *parent;
int i,root_src,root_dest,nedges;
parent=new int;
for(i=0;i parent[i]=i;
cur=phead->next;
while(cur && cur->src==cur->dest)
cur=cur->next;
if (!cur)
error(err);
first=cur;
parent[first->dest]=first->src;
nedges=1;
cur=first->next;
first->next=NULL;
while(cur||nedges {
temp=cur->next;
root_src=root(parent,cur->src);
root_dest=root(parent,cur->dest);
if(root_dest!=root_src)
{
cur->next=first;
first=cur;
parent[root_dest]=root_src;
nedges++;
}else
delete cur;
cur=temp;
}
phead->next=first;
return nedges;
}
void main()
{
int n;
ll_node head;
ll_node *cur;
clrscr();
head.next=NULL;
n=input(&head);
if(min_span(&head,n)!=n-1)
error(err);
cur=head.next;
cout<<"The minimum spanning tree has the following edges\n";
while(cur)
{
cout<src+1<<"-"<dest+1<<"-"<weight;
cur=cur->next;
}
}
Output for KRUSHKAL
Input the edges as :
Input non-numerals to terminate 1 2 3
123 2 3 4
234 3 4 5
345 4 1 6
416 4 2 7
427

The minimum spanning tree has the following edges

3-4-5
2-3-4
1-2-3