#include
#include
intvisited[30]={0};
intno,cost=0,count=0;
structgraph
{
intnode_no;
structvertex*h_link;
structgraph*v_link;
}*header=NULL,*current=NULL,*s0,*s1;
structvertex
{
intnode_no;
intcost;
structvertex*link;
}*min=NULL;
structnode
{
intdata;
intcost;
structnode*link1;
structnode*link2;
}*root=NULL,*cr,*mincr;
voidinsertvertex(intd)
{
structgraph*p,*q;
p=(structgraph*)malloc(sizeof(structgraph));
p->node_no=d;
p->h_link=NULL;
if(header==NULL)
{
header=p;
p->v_link=NULL;
}
else
{
p->v_link=header;
header=p;
}
}
voidinsertcon(intvn,intcos)
{
structvertex*p,*q,*pr=NULL;
p=(structvertex*)malloc(sizeof(structvertex));
p->cost=cos;
p->node_no=vn;
p->link=NULL;
if(header->h_link==NULL)
{
header->h_link=p;
}
else
{
q=header->h_link;
while(q!=NULL&&q->costlink;
}
p->link=q;
if(pr!=NULL)
pr->link=p;
else
header->h_link=p;
}
//if(vn==2)
//printf("nodeno=%p\n",pr);
}
voidsetup(structgraph*s)
{
structvertex*p,*q;
structnode*n1,*n2;
p=s->h_link;
q=p->link;
n1=(structnode*)malloc(sizeof(structnode));
n2=(structnode*)malloc(sizeof(structnode));
root=n1;
n1->data=s->node_no;
n1->cost=0;
n1->link1=n2;
n1->link2=NULL;
visited[s->node_no]=1;
n2->data=p->node_no;
n2->cost=p->cost;
cost+=p->cost;
n2->link1=NULL;
n2->link2=NULL;
min=q;
s=header;
while(s->node_no!=n2->data)
s=s->v_link;
current=s;
count=2;
visited[n2->data]=1;
cr=n2;
mincr=root;
}
voidbuild()
{
while(count!=no){
structnode*n3,*gfs;
n3=(structnode*)malloc(sizeof(structnode));
structvertex*t1,*tt,*c01;
c01=current->h_link;
while(c01!=NULL&&visited[c01->node_no]==1)
c01=c01->link;
if(c01==NULL)
{c01=min;min=NULL;cr=mincr;}
else{
t1=min;
if(min!=NULL)
if(c01->cost>t1->cost)
{tt=c01;c01=min;min=tt;gfs=cr;cr=mincr;mincr=gfs;}}
if(cr->link1==NULL)
cr->link1=n3;
else
cr->link2=n3;
n3->data=c01->node_no;
n3->cost=c01->cost;
cost+=c01->cost;
visited[n3->data]=1;
n3->link1=NULL;
n3->link2=NULL;
c01=c01->link;
while(c01!=NULL&&visited[c01->node_no]==1)
c01=c01->link;
count++;
s1=current;
s0=header;
while(s0->node_no!=n3->data)
s0=s0->v_link;
current=s0;
if(c01!=NULL&&c01->costcost)
{min=c01;mincr=cr;}
cr=n3;
}
}
voidprintree(structnode*r)
{
if(r!=NULL)
{
printree(r->link1);
printf("%d\n",r->data);
printree(r->link2);
}
}
voidmain()
{
inti,d,j,cos,nc,vn,sv;
structgraph*g=NULL,*start;
structvertex*gv=NULL,*g1=NULL;
structnode*p1,*p2,*p3;
printf("Enternoofvertices");
scanf("%d",&no);
for(i=0;i0)
printf("Entertheconnections\n");
for(j=0;jnode_no!=sv)
start=start->v_link;
if(start!=NULL){
setup(start);
build();
printf("\nInorderTraversaloftree\n")
printree(root);
}
printf("Costis%d",cost);
}
/*justtocheckwhetherI/pisstoredproperly
g=header;
while(g!=NULL)
{
printf("%d::",g->node_no);
g1=g->h_link;
while(g1!=NULL)
{
printf("%d->",g1->node_no);
g1=g1->link;
}
g=g->v_link;
printf("\n");
}*/
/*maynotworkforexceptionalcases*/
