/* C Program On Krushkal's Algorithm */
#include < stdio.h>
#include < conio.h>
typedef struct
{
int node1;
int node2;
int wt;
}edge;
void sortedges(edge a[],int n)
{
int i,j;
edge temp;
for(i=0;i< n-1;++i)
for(j=i+1;j< n;++j)
if(a[i].wt>a[j].wt){temp=a[i];a[i]=a[j];a[j]=temp;}
}
int checkcycle(int p[],int i,int j)
{
int v1,v2;
v1 = i;
v2 = j;
while(p[i]>-1)
i = p[i];
while(p[j]>-1)
j = p[j];
if(i!=j)
{
p[j]=i;
printf("%d %d\n",v1,v2);
return 1;
}
return 0;
}
void main()
{
edge e[100];
int parent[100];
int n,i,j,m,k = 1,cost = 0;
clrscr();
printf("KRUSKAL's ALGORITHM\n");
printf("Enter number of nodes\n");
scanf("%d",&n);
for(i=0;i< n;++i)
parent[i]=-1;
i = 0;
printf("Enter number of edges\n");
scanf("%d",&m);
for(i=0;i< m;++i)
{
printf("enter an edge and wt\n");
scanf("%d %d %d", &e[i].node1,&e[i].node2,&e[i].wt);
}
sortedges(e,m);
printf("\n\nEdges of the tree\n");
i = 0;
while(k< n)
{
if(checkcycle(parent,e[i].node1,e[i].node2))
{
k++;
cost=cost+e[i].wt;
i++;
}
}
printf("cost = %d",cost);
getch();
}
Subscribe to:
Post Comments (Atom)
15 comments:
thanks a lot sir...i really get benifited with ur programmes...
thanx sir 4 ur useful programmes...i benefited a lot...
Wow....thnx...dis is really simple and efficient.^_^
Thank u sir Thank u so much
thanks sir.. really helpful..
nice job
the program doesn't give error message if the graph is not connected.. what addition should be added sir..
the program doesn't give error message if the graph is not connected.. what addition should be added sir..
while(p[i]>-1)
i = p[i];
while(p[j]>-1)
j = p[j];
I just wanted to know what does this condition is for?
Program goes into infinite loop at that point of code....
Easy One!!
HelpFul!
hell......this program is entering into a infinite loop!!!!!!
#include
#include
typedef struct
{
int node1;
int node2;
int wt;
}edge;
void sortedges(edge a[],int n)
{
int i,j;
edge temp;
for(i=0;i< n-1;i++)
{
for(j=i+1;j< n;j++)
{
if(a[i].wt>a[j].wt)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
int checkcycle(int p[],int i,int j)
{
int v1,v2;
v1=i;
v2=j;
while(p[i]>-1)
i = p[i];
while(p[j]>-1)
j = p[j];
if(i!=j)
{
p[j]=i;
printf("%d %d\n",v1,v2);
return 1;
}
return 0;
}
void main()
{
edge e[100];
int parent[100];
int n,i,j,m,k = 1,cost = 0;
clrscr();
printf("KRUSKAL's ALGORITHM\n");
printf("Enter number of nodes\n");
scanf("%d",&n);
for(i=0;i< n;i++)
parent[i]=-1;
i=0;
printf("Enter number of edges\n");
scanf("%d",&m);
for(i=0;i< m;++i)
{
printf("enter the nodes n1 & n2 & wt\n");
scanf("%d %d %d", &e[i].node1,&e[i].node2,&e[i].wt);
}
sortedges(e,m);
printf("\n\nEdges of the tree\n");
i=0;
while(k<m)
{
checkcycle(parent,e[i].node1,e[i].node2);
k++;
cost=cost+e[i].wt;
i++;
}
printf("cost = %d",cost);
getch();
}
Thanks a lot sir for writing this simple yet elegant piece of code.I shall also like to suggest a few tiny modifications that will help the code not entering into infinite loops as I noticed in some test cases. I am giving this modified code as below....
/* C Program On Krushkal's Algorithm */
#include < stdio.h>
#include < conio.h>
typedef struct
{
int node1;
int node2;
int wt;
}edge;
void sortedges(edge a[],int n)
{
int i,j;
edge temp;
for(i=0;i< n-1;++i){
for(j=i+1;j< n;++j)
if(a[i].wt>a[j].wt){temp=a[i];a[i]=a[j];a[j]=temp;}
}
printf("\nSorted edges are:\n");
for(i=0;i-1)
i = p[i];
while(p[j]>-1)
j = p[j];
if(i!=j)
{
p[j]=i;
printf("%d %d\n",v1,v2);
return 1;
}
else{ //Modification //made by including the else clause
return 0;}
}
void main()
{
edge e[100];
int parent[100];
int n,i,j,m,k = 1,cost = 0;
printf("KRUSKAL's ALGORITHM\n");
printf("Enter number of nodes\n");
scanf("%d",&n);
for(i=0;i< n;++i)
parent[i]=-1;
i = 0;
printf("Enter number of edges\n");
scanf("%d",&m);
for(i=0;i< m;++i)
{
printf("enter an edge and wt\n");
scanf("%d %d %d", &e[i].node1,&e[i].node2,&e[i].wt);
}
sortedges(e,m);
printf("\n\nEdges of the tree\n");
i = 0;
while(k< n)
{
if(checkcycle(parent,e[i].node1,e[i].node2))
{
k++;
cost=cost+e[i].wt;
}
i++;//Modification made by //incrementing i outside the if //clause
}
printf("cost = %d",cost);
getch();
}
thank's a lot it's working
fantastic put up, very informative. I'm wondering why the opposite experts of this sector do not realize this. You should continue your writing. I'm confident, you've a huge readers' base already!
Also visit my web-site - sushi cat 3 armor games
Post a Comment