Kruskal’s Algorithm is a greedy algorithm used to find a minimum spanning tree in a connected, undirected graph.
• The algorithm operates by repeatedly adding the smallest edge that does not form a cycle with the edges already chosen.
• Its simplicity, optimality, and efficiency make it a popular choice for various applications in network design, optimization, and resource allocation.
Steps for finding MST using Kruskal’s algorithm:
- Sort all the edges in non-decreasing order of their weight.
- Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If the cycle is not formed, include this edge. Else, discard it.
- Repeat step#2 until there are (n-1) edges in the spanning tree.
For example:
Step 1: Sort all the edges in non-decreasing order of their weight.
| Edges | Weight |
|---|---|
| BC | 1 |
| BD | 2 |
| DE | 3 |
| AB | 4 |
| CD | 6 |
| AD | 10 |
Step 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If the cycle is not formed, include this edge. Else, discard it.
Here BC is the smallest edge.
Again, Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If the cycle is not formed, include this edge. Else, discard it.
Here BD is the smallest edge.
Again, Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If the cycle is not formed, include this edge. Else, discard it.
Here DE is the smallest edge.
Again, Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If the cycle is not formed, include this edge. Else, discard it.
Here AB is the smallest edge.
Note:- if we add AD or CD it will form cycle or loop that discards the property of MST so we discard these edges.
So, this is the minimum spanning tree of the given graph. The cost of the MST is given below –
Cost of MST = 4 + 2 + 1 + 3 = 10 units.
Applications:
- Network design and optimization.
- Circuit design in electronic networks.
- Approximating solutions for the traveling salesman problem.
