Data Structure

# Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph.
It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
This algorithm is directly based on the MST( minimum spanning tree) property.

### Example

 A Simple Weighted Graph Minimum-Cost Spanning Tree

### Kruskal's Algorithm

```MST-KRUSKAL(G, w)
1.	A ← Ø
2.	for each vertex v  V[G]
3.		do MAKE-SET(v)
4.	sort the edges of E into nondecreasing order by weight w
5.	for each edge (u, v)  E, taken in nondecreasing order by weight
6.		do if FIND-SET(u) ≠ FIND-SET(v)
7.			then A ← A  {(u, v)}
8.				UNION(u, v)
9.	return A
```

### Example

#### Procedure for finding Minimum Spanning Tree

Step1. Edges are sorted in ascending order by weight.
Edge No.Vertex PairEdge Weight
E1(0,2)1
E2(3,5)2
E3(0,1)3
E4(1,4)3
E5(2,5)4
E6(1,2)5
E7(2,3)5
E8(0,3)6
E9(2,4)6
E10(4,5)6

Step2. Edges are added in sequence.
Total Cost = 1+2+3+3+4 = 13s

### C IMPLEMETATION of Kruskal's Algorithm

```#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main()
{
clrscr();
printf("\n\tImplementation of Kruskal's algorithm\n");
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost adjacency 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]=999;
}
}
printf("The edges of Minimum Cost Spanning Tree are\n");
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;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
getch();
}
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
```

### output

`About Me`