= Solution
<Kruskal's algorithm> sorts the edges and accepts an edge precisely when it joins two currently different <connected components of a graph>. A <disjoint-set data structure> maintains those components:
``
Kruskal(V, E, w):
A = empty set
make one disjoint set for each vertex in V
for (u,v) in E sorted by nondecreasing w:
if find(u) != find(v):
add (u,v) to A
union(u,v)
if size(A) == size(V) - 1:
break
return A
``
An accepted edge merges two trees of the current <forest>. An edge within one component would complete a <graph cycle> and is skipped. On connected input, after $|V|-1$ acceptances the forest is a spanning tree. For a one-vertex graph the empty set is already the answer.
Back to article page
