Your Ad Here

Sunday, June 1, 2008

Krushkal's Algorithm

/* 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();
}

15 comments:

Anonymous said...

thanks a lot sir...i really get benifited with ur programmes...

Anonymous said...

thanx sir 4 ur useful programmes...i benefited a lot...

arkydon said...

Wow....thnx...dis is really simple and efficient.^_^

Anonymous said...

Thank u sir Thank u so much

radha said...

thanks sir.. really helpful..

Anonymous said...

nice job

Unknown said...

the program doesn't give error message if the graph is not connected.. what addition should be added sir..

Unknown said...

the program doesn't give error message if the graph is not connected.. what addition should be added sir..

anoopnyati said...

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....

Mouyse said...

Easy One!!
HelpFul!

Anonymous said...

hell......this program is entering into a infinite loop!!!!!!

Mestar said...

#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();
}

samratphysics said...

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();
}

Anonymous said...

thank's a lot it's working

Anonymous said...

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

Your Ad Here