Trend Posts
Author
View LUQMAN's profile
Showing posts with label kruskals algorithm. Show all posts
Showing posts with label kruskals algorithm. Show all posts
Monday, July 21, 2014
/*Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm.*/
#include<stdio.h>
int ne,i,j,min,u,v,cost[100][100],n,a,b,parent[100],mincost=0;
void kruskal()
{
ne=1;
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
while(parent[u])
u=parent[u];
while(parent[v])
v=parent[v];
if(u!=v)
{
printf("%d>minimum edge from %d to %d is %d\n",ne++,a,b,min);
mincost+=min;
parent[v]=u;
}
cost[a][b]=cost[b][a]=999;
}
}
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the weight of each nodes\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\nEntered weights are:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
kruskal();
}
Subscribe to:
Posts (Atom)