Kruskal’s Algorithm
It is a minimum spanning subtree algorithm.
It performs well for sparse graphs due to simple data structures: .
The way it works:
- Choose the shortest edge.
- Choose the next shortest edge, ensure it does not form a cycle in the subtree formed so far. If a cycle is formed, discard the edge.
- Repeat step 2 until there are edges in the subtree.
