Step-by-step 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 steps 2 and 3 until there are (V-1) edges in the spanning tree.
Kruskal’s Algorithm in Python
Kruskal’s Algorithm is used to find Minimum Spanning Tree in the graph. A minimum spanning tree (MST) is a spanning tree with a weight less than or equal to the weight of every other spanning tree.
Examples:
Input: N = 6, edges[][] = {{1, 2, 1}, {2, 3, 4}, {1, 4, 3}, {4, 5, 6}, {2, 5, 2}, {3, 5, 5}, {5, 6, 6}}
Output: MST with edges: {{1, 2, 1}, {2, 3, 4}, {1, 4, 3}, {2, 5, 2}, {5, 6, 6}}