= Kruskal component merging
{c}
A <disjoint-set data structure> stores the current <partition of a set> of <vertices> into <connected components of a graph>. The operation $\operatorname{find}(v)$ returns a representative of the block containing $v$. Two <vertices> are in the same block exactly when their representatives agree. For each candidate <edge> $uv$, compare $\operatorname{find}(u)$ and $\operatorname{find}(v)$. Equal representatives mean reject; different representatives mean accept and perform $\operatorname{union}(u,v)$, merging the two blocks. The representatives are bookkeeping choices, not preferred <vertices> of the <minimum spanning tree>.
\Image[/kruskal-component-merge-ledger.png]
{title=<Connected components of a graph> merge only when an <edge> is accepted}
{description=The same example as a <disjoint-set data structure> ledger. Each coloured band is one block of the current <partition of a set>. The rejection of $AC$ leaves both the <partition of a set> and the running cost unchanged. Bands show membership, not internal representative pointers.}
Every acceptance reduces the <connected component of a graph> count by one and increases the accepted <edge> count by one, preserving $|F|=|V|-c$. Thus the ledger reaches $c=1$ exactly when $|F|=4$. Only ten representative queries and four merges are needed for the five examined <edges>, counting two queries per examination and using the already found representatives for each merge. Neither <breadth-first search> nor reconstruction of a <graph path> is needed for these connectivity queries.
For $n=|V|$ and $m=|E|$, comparison <sorting algorithm> takes $O(m\log m)$ time for $m\geq2$, using <Big O notation>. One simple <disjoint-set data structure> implementation stores each block as a <rooted tree> and attaches the smaller block's root below the larger block's root. Whenever a <vertex>'s depth increases, its block size at least doubles, so its depth is at most $\lfloor\log_2 n\rfloor$. Consequently each representative query or merge takes $O(\log n)$ time. Initialization plus the scan costs $O(n+m\log n)$; including <sorting algorithm> gives $O(n+m\log m+m\log n)$, hence $O(m\log m)$ for a connected input with $n\geq2$. These are operation bounds, not measured timings.<Algorithms, 4th edition by Robert Sedgewick and others/WeightedQuickUnionUF.java>[Robert Sedgewick and Kevin Wayne, Algorithms, 4th edition, companion WeightedQuickUnionUF.java: class documentation and union method; union by size without path compression, linear initialization and logarithmic operations]{ref}
Back to article page
