6.11 PRIMS ALGORITHM

#include
#include
#include
#include
class ll_node
{
public:
int scr,dest,weight;
ll_node *next;
};
int *parent;
char err[]="some nodes are isolated";
void error(char *msg)
{
puts(msg);
exit(1);
}
void put_sorted(ll_node *phead,ll_node *node)
{
ll_node *prev,*cur;
prev=phead;
cur=phead->next;
while(cur && cur->weight < node->weight)
{
prev=cur;
cur=cur->next;
}
node->next=cur;
prev->next=node;
}
int input(ll_node *phead)
{
int p=0,i,j,n=0,w;
ll_node *node;
char inps[80];
puts("\n input adjacency matrix on node list\n");
do
{
p=1;
cout<<"enter no of nodes:";
cin>>n;
cout<<"input adjacency matrix"< for(i=0;i {
cout<<"row"< for(j=0;j {
cin>>w;
if(w)
{
node=new ll_node;
node->scr=i;
node->dest=j;
node->weight=w;
put_sorted(phead,node);
}
}
}
}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_scr,root_dest,nedges;
parent=new int;
for(i=0;i parent[i]=i;
cur=phead->next;
while(cur && cur->scr==cur->dest)
cur=cur->next;
if(!cur)
error(err);
first=cur;
parent[first->dest]=first->scr;
nedges=1;
cur=first->next;
first->next=NULL;
while(cur||nedges<1)
{
temp=cur->next;
root_scr=root(parent,cur->scr);
root_dest=root(parent,cur->dest);
if(root_dest!=root_scr)
{
cur->next=first;
first=cur;
parent[root_dest]=root_scr;
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<<"\nthe minimum spanning tree by prims \n";
while(cur)
{
cout<scr+1<<"-"<dest+1<<"-"<weight;
cur=cur->next;
}
getch();
}

Sample input and output
Output of PRIMS

input adjacency matrix on node list

enter no of nodes:4
input adjacency matrix
row1 0 3 0 6
row2 3 0 4 7
row3 0 4 0 5
row4 6 7 5 0

the minimum spanning tree by prims

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