Description:
Kruskal's
algorithm is a minimum-spanning-tree algorithm which finds an edge of the
least possible weight that connects any two trees in the forest.
Algorithm
Let G =
(V, E) be the given graph, with | V| = n
{
Start with a graph T = (V,â±·) consisting of only the
vertices of G and no edges; /* This can be viewed as n
connected components, each vertex being one connected component */
Arrange E in the order of increasing
costs;
for (i = 1, i≤n -
1, i + +)
{
Select the next smallest cost edge;
if the edge connects two different
connected components
add the edge to T;
}
}
Solution:
#include<stdio.h>
int parent[20],min,mincost=0,ne=1,n,cost[20][20];
int a,b,i,j,u,v;
void main()
{
printf("Enter the no of nodes\n");
scanf("%d",&n);
printf("Enter the cost matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=99;
}
while(ne <n)
{
for(i=1,min=99;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\t
edge \t (%d,%d)=%d\n",ne++,a,b,min);
mincost+=min;
parent[v]=u;
}
cost[a][b]=cost[b][a]=99;
}
printf("The minimum
cost=%d\n",mincost);
}
OUTPUT 1:
Enter the no of nodes
7
Enter the cost matrix
0 28 99 99 99 10 99
28 0 16 99 99 99 14
99 16 99 12 99 99 99
99 99 12 0 22 99 18
99 99 99 22 0 25 24
10 99 99 99 25 0 99
99 14 99 18 24 99 0
1 edge (1,6)=10
2 edge (3,4)=12
3 edge (2,7)=14
4 edge (2,3)=16
5 edge (4,5)=22
6 edge (5,6)=25
The minimum cost=99
OUTPUT 2
Enter the no of nodes
3
Enter the cost matrix
0 10 1
10 0 6
1 6 0
1 edge (1,3)=1
2 edge (2,3)=6
The minimum cost=7
No comments:
Post a Comment