Initially, each vertex is in a set all by itself: There is a singleton set {v}
for every vertex v
. In the pseudo-code, these sets are the result of make_set(v)
.
For a given vertex v
, the function find_set(v)
gives you the set containing v
.
The algorithm merges sets iteratively, so if {u}
, {v}
are singleton sets initially and there is an edge (u, v)
, then the algorithm replaces the two sets by their union {u, v}
. Now both find_set(u)
and find_set(v)
will return that set.
The algorithm terminates after you've added |V| - 1
non-trivial edges, which is precisely the number of edges in a tree.