Kruskal's Algorithm
# Kruskal’s Algorithm
# General Idea
A greedy algorithm to generate a Minimum Spanning Tree using the Union Find data structure.
- Sort edges in increasing order of weight (a priority queue using a Heaps)
- Add the edge to the minimum spanning tree unless it creates a cycle
- Cycle check uses union find
# Pseudocode
# Complexity
Time complexity is $O(ElogE)$ mainly due to the contribution of the Heaps implementation of priority queue to obtain the least cost edge.
# Examples
Manually:
Update the id directly to the root (D) when connecting with other equivalence classes when using
:
