Kruskal's Algorithm

Summarized notes on Introduction to Algorithms, Chapter 23

• choose the least-weight edge that connecting distinct components $C_1$ and $C_2$
• implement using disjoint sets where each set represents a tree
  • when vertices $u$ and $v$ have different representative they belong to different sets
  • edge $(u,v)$ is safe to add to $A$
• optimal time when using union by rank and path compression

Example

Complexity

Running time
$O(V)$	initialize sets -- $O(1)$ $V$ times
$O(E\lg V)$	sort sets
$O(E\alpha (V))$	set operations to find and union
$O(E\lg V)$	= Kruskal's algorithm