#include<stdio.h>
struct graph
{
int u,v,wt,select;
}x[30];
int n1,n2,rootn1,rootn2,mincost;
void sort(struct graph x[30],int n)
{
struct graph temp;
int i,j;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
if(x[j],wt>x[j+1],wt)
{
temp=x[j];
x[j]=x[j+1];
x[j+1]=temp;
}
}
}
}
main()
{
int w,k=1,n,c=0,i,j;
printf("\n\tEnter the number of nodes");
scanf("%d",&n);
printf("\n\t\tEnter the weights\n");
scanf("%d",&n);
printf("\n\tEnter the weights\n");
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
printf("\t\t\t\t%d->%d = ",i,j);
scanf("%d",&w);
if(w>0)
{
x[k],u=i;
x[k],v=j;
x[k],select=0;
x[k],wt=w;
k++;
}
}
}
sort(x,k);
printf("\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;
printf("\n\t\t\t%d->%d=%d",x[i],u,x[i],v,x[i],wt);
mincost+=x[i],wt;
c++;
}
}
printf("\n\t\tMinimum cost =%d",mincost);
return(0);
}
/*
----------------------------------------------------------------------------------------------
OUTPUT
------
Enter the number of 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=2
1->2=2
2->3=2
Minimal cost=5
----------------------------------------------------------------------------------------------
struct graph
{
int u,v,wt,select;
}x[30];
int n1,n2,rootn1,rootn2,mincost;
void sort(struct graph x[30],int n)
{
struct graph temp;
int i,j;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
if(x[j],wt>x[j+1],wt)
{
temp=x[j];
x[j]=x[j+1];
x[j+1]=temp;
}
}
}
}
main()
{
int w,k=1,n,c=0,i,j;
printf("\n\tEnter the number of nodes");
scanf("%d",&n);
printf("\n\t\tEnter the weights\n");
scanf("%d",&n);
printf("\n\tEnter the weights\n");
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
printf("\t\t\t\t%d->%d = ",i,j);
scanf("%d",&w);
if(w>0)
{
x[k],u=i;
x[k],v=j;
x[k],select=0;
x[k],wt=w;
k++;
}
}
}
sort(x,k);
printf("\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;
printf("\n\t\t\t%d->%d=%d",x[i],u,x[i],v,x[i],wt);
mincost+=x[i],wt;
c++;
}
}
printf("\n\t\tMinimum cost =%d",mincost);
return(0);
}
/*
----------------------------------------------------------------------------------------------
OUTPUT
------
Enter the number of 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=2
1->2=2
2->3=2
Minimal cost=5
----------------------------------------------------------------------------------------------
aap bhi chu hoo.>!!
ReplyDeleteWhat's the father array in this??
ReplyDelete#include
ReplyDelete#include
#include
int edges[20][3];
int e_no=-1;
int mst[20][2];
int m_no=-1;
struct set
{
int element[20];
int index;
struct set* link;
};
struct set *header,*current;
void make_set(int x)
{
struct set *new_set;
new_set=(struct set*)malloc(sizeof(struct set));
new_set->index=0;
new_set->element[new_set->index]=x;
new_set->link=NULL;
current->link=new_set;
current=new_set;
}
struct set* find_set(int x)
{
struct set *itr;
int i;
itr=header->link;
while(itr!=NULL)
{
for(i=0;i<=itr->index;i++)
{
if(itr->element[i]==x)
return itr;
}
itr=itr->link;
}
return NULL;
}
void set_union(struct set* ptr1,struct set* ptr2)
{
struct set *itr,*from;
int i,j;
from=header;
itr=header->link;
while(from->link!=ptr1&&itr!=NULL)
{
from=itr;
itr=itr->link;
}
i=ptr2->index+1;
j=0;
while(j<=ptr1->index)
{
ptr2->element[i]=ptr1->element[j];
i++;
j++;
ptr2->index++;
}
from->link=itr->link;
}
void read_graph(int n)
{
int i,j,c,w;
for(i=0;iedges[j+1][2])
{
t=edges[j+1][0];
edges[j+1][0]=edges[j][0];
edges[j][0]=t;
t=edges[j+1][1];
edges[j+1][1]=edges[j][1];
edges[j][1]=t;
t=edges[j+1][2];
edges[j+1][2]=edges[j][2];
edges[j][2]=t;
}
}
}
}
int main()
{
struct set *p1,*p2;
int v_no,i;
header=(struct set*)malloc(sizeof(struct set));
current=header;
printf("\n\n\tEnter the no of vertices : ");
scanf("%d",&v_no);
read_graph(v_no);
sort();
for(i=0;i<v_no;i++)
make_set(i);
for(i=0;i<e_no;i++)
{
p1=find_set(edges[i][0]);
p2=find_set(edges[i][1]);
if(p1!=p2)
{
m_no++;
mst[m_no][0]=edges[i][0];
mst[m_no][1]=edges[i][1];
set_union(p1,p2);
}
}
printf("\n\n\tMST edges : ");
for(i=0;i<=m_no;i++)
printf(" (v%d,v%d)",mst[i][0],mst[i][1]);
getch();
}
what is "father"???
ReplyDeleteask mother
Deletecode is incorrect
ReplyDelete