Kruskal's Running Time And Sorting Costs

Separate Sorting from Edge Processing

Kruskal’s algorithm has two distinct tasks: arrange the edges by weight, then scan them in that order while using a disjoint-set data structure to decide whether an edge joins two different components. The sorting cost can dominate when the input is unsorted. If the edges are already supplied in nondecreasing order, that sorting step is unnecessary, but the algorithm still has to inspect edges and perform disjoint-set operations.

Throughout, let $G=(V,E)$ be a finite, simple, undirected graph with $n=|V|$ vertices and $m=|E|$ edges. Each edge has a weight. Kruskal’s algorithm processes edges in nondecreasing weight order, accepting an edge when its endpoints are in different current components and rejecting it otherwise. On a connected graph, the accepted edges form a minimum spanning tree; on a disconnected graph, they form a minimum spanning forest, with one tree in each component. The correctness of this choice is established by the cut-property argument for Kruskal’s algorithm.

Definition: In a disjoint-set data structure, Find$(v)$ identifies the current set containing $v$, and Union$(u,v)$ merges the sets containing $u$ and $v$, when they are distinct. Kruskal’s test for an edge $uv$ is whether $\operatorname{Find}(u)$ and $\operatorname{Find}(v)$ identify different sets.

Initially, each vertex is in its own set. After an edge is accepted, the two endpoint sets are merged. An edge is rejected precisely when its endpoints are already in the same set. This test prevents the accepted edges from making a cycle.

How Many Disjoint-Set Operations Occur?

Assume first that the algorithm scans the entire edge list, rather than stopping early. Each of the $m$ edges requires two Find operations, one for each endpoint. Thus there are exactly $2m$ endpoint Find calls. Every accepted edge causes one Union. If the original graph has $c$ connected components, including isolated vertices, the number of accepted edges is $n-c$, so the scan makes $n-c$ Union calls.

Proposition: After a full scan of the edges, Kruskal’s algorithm has made $2m$ endpoint Find calls and $n-c$ Union calls, where $c$ is the number of connected components of $G$. This count assumes that each accepted edge invokes one Union, and that Union is not counted as an additional pair of endpoint Find calls.

Proof. Initially there are $n$ singleton sets. Each accepted edge joins two different sets, so it reduces the number of sets by exactly one. A rejected edge does not change the sets. At the end, two vertices are in the same disjoint set exactly when they are connected by edges of $G$: accepted edges preserve the connectivity of every processed edge, since a rejected edge already has endpoints connected by accepted edges. Therefore the final sets are the $c$ connected components of $G$. Reducing the number of sets from $n$ to $c$ takes exactly $n-c$ successful unions. Every edge is tested once and requires two endpoint Find calls, giving $2m$ calls. If $n=0$, then $m=c=0$, and both counts are zero. $\square$

This count is useful independently of the implementation. A particular implementation might perform extra Find calls inside a Union routine. In that case, those internal calls must be added to the cost estimate; the $2m$ count refers to the endpoint tests in the edge scan.

Turning Operation Counts into Running Time

Initializing a disjoint-set structure takes $O(n)$ time. A simple implementation using union by size has a logarithmic worst-case bound for Find. To see why, consider the depth of an element in the parent structure. Whenever its depth increases, its set is merged into another set at least as large, so the size of its set at least doubles. A set has at most $n$ elements, so an element’s depth can increase at most $\lfloor\log_2 n\rfloor$ times. A Find follows parent pointers up to the root, and therefore takes $O(\log n)$ time in this implementation. A Union uses Find to locate the roots and then attaches the smaller set beneath the larger one, so it also takes $O(\log n)$ time in this bound.

Consequently, with union by size, initializing and processing all edges costs $O(n+(m+n)\log n)$ for $n\ge2$, before accounting for sorting. This is a valid, elementary bound, but implementations commonly use both union by rank (or size) and path compression. For that optimized structure, Tarjan’s standard disjoint-set bound states that a sequence of $p$ Find and Union operations on $n$ elements takes $O(p\,\alpha(n))$ amortized time, where $\alpha$ is the inverse Ackermann function. “Amortized” means that this bound applies to the total cost of a sequence of operations, not necessarily to each individual operation. The proof of this technical data-structure result is outside this tutorial.

Theorem: Using comparison sorting and a disjoint-set structure with union by rank and path compression, a full run of Kruskal’s algorithm takes $$ O\bigl(n+m\log(m+1)+(m+n)\alpha(n)\bigr) $$ time. If the edges are already in nondecreasing weight order, it takes $$ O\bigl(n+(m+n)\alpha(n)\bigr) $$ time, without the sorting cost.

Proof. Comparison sorting $m$ edge weights takes $O(m\log(m+1))$ time; the $+1$ keeps the expression defined when $m=0$. Initializing the disjoint-set structure takes $O(n)$ time. The full edge scan makes $2m$ endpoint Find calls and $n-c$ Union calls by the proposition, for a total of $2m+n-c\le 2m+n$ operations. Applying the stated standard disjoint-set bound gives $O((m+n)\alpha(n))$ time for these operations. Adding the sorting and initialization costs gives the first bound. If the input is already sorted, no comparison sort is needed, so the same initialization and disjoint-set costs give the second bound. When $n=0$, the algorithm has no edges or operations and takes constant time; the displayed asymptotic bounds are intended for $n\ge1$. $\square$

For a connected simple graph with $n\ge2$, $m\ge n-1$, and simplicity gives $m\le n(n-1)/2$. Thus $\log(m+1)=O(\log n)$, and the comparison-sort bound simplifies to $O(m\log n)$. This familiar shorthand assumes connected input and $n\ge2$. For a disconnected graph with many isolated vertices, initialization still costs $O(n)$, so retaining the $n$ term is important. If there are no edges, sorting and scanning have no edge work at all, but the stated implementation still initializes the $n$ vertices.

Worked Operation Counts

Worked Example: Six Edges and Four Unions

Let $V=\{1,2,3,4,5\}$. Give the edges weights $w(12)=1$, $w(23)=2$, $w(34)=3$, $w(45)=4$, $w(13)=5$, and $w(24)=6$. The list is already sorted. Trace Kruskal’s scan and count its endpoint operations.

Initially the sets are $\{1\},\{2\},\{3\},\{4\},\{5\}$. The edge $12$ joins distinct sets, so accept it and merge them. The edge $23$ then joins $\{1,2\}$ to $\{3\}$, so accept it. The edge $34$ joins $\{1,2,3\}$ to $\{4\}$, so accept it. The edge $45$ joins $\{1,2,3,4\}$ to $\{5\}$, so accept it. Now all vertices are in one set. The edge $13$ has both endpoints in that set, so reject it; the edge $24$ also has both endpoints in that set, so reject it.

There are $m=6$ scanned edges, and each edge makes two endpoint Find calls, giving $2\cdot6=12$ Find calls. The four accepted edges $12,23,34,45$ each trigger one Union, so there are $4$ Union calls. The output is the spanning tree with those four edges, and its weight is $1+2+3+4=10$. As a check on the operation count, $n=5$ and $c=1$, so $n-c=5-1=4$ unions, agreeing with the trace.

Worked Example: A Sorted List for a Disconnected Graph

Let $V=\{1,2,3,4,5,6\}$, with edges $12,23,13,45,56,46$, of weights $1,2,3,4,5,6$, respectively. The input is already sorted. The graph consists of two triangles, so it has $n=6$, $m=6$, and $c=2$.

Start with six singleton sets. Accept $12$, merging $\{1\}$ and $\{2\}$. Accept $23$, merging $\{1,2\}$ and $\{3\}$. Reject $13$, since its endpoints are now in the same set. Accept $45$, merging $\{4\}$ and $\{5\}$. Accept $56$, merging $\{4,5\}$ and $\{6\}$. Reject $46$, since $4$ and $6$ are already in the same set.

The selected forest is $\{12,23,45,56\}$, with total weight $1+2+4+5=12$. In each triangle it selects the two lower-weight edges and rejects the third, so each component’s selected edges connect its three vertices without a cycle. There are $2\cdot6=12$ endpoint Find calls and $4$ Union calls. Independently, the count formula gives $n-c=6-2=4$ unions. The edge list required no sorting, but all six edges still had to be tested in this full-scan version.

Worked Example: Sorting an Unordered Edge List

Let $V=\{1,2,3,4,5\}$, with edges and weights, in the given input order, $12:4,\ 23:1,\ 34:3,\ 45:2,\ 13:6,\ 24:5,\ 15:7$. To make the sorting cost concrete, use insertion sort on this list of weights.

Insert $1$ before $4$: this takes one comparison. Insert $3$: compare it with $4$, then with $1$, for two comparisons. Insert $2$: compare with $4$, then $3$, then $1$, for three comparisons. Insert $6$: compare with $4$ and stop, for one comparison. Insert $5$: compare with $6$, then $4$, for two comparisons. Insert $7$: compare with $6$ and stop, for one comparison. The total is $1+2+3+1+2+1=10$ comparisons. The sorted edge order is $23:1,\ 45:2,\ 34:3,\ 12:4,\ 24:5,\ 13:6,\ 15:7$.

Kruskal accepts $23$, then $45$, then $34$, which merges the two current components into $\{2,3,4,5\}$. It accepts $12$, joining vertex $1$ to that component. It rejects $24$, $13$, and $15$, because the endpoints of each are already connected. The output edges $23,45,34,12$ form the path $1,2,3,4,5$; their total weight is $1+2+3+4=10$. There are seven scanned edges, so $2\cdot7=14$ endpoint Find calls, and four accepted edges, so four Union calls. The operation count also agrees with $n-c=5-1=4$. The ten insertion-sort comparisons are the cost of this specified sorting method on this input; a different comparison-sorting algorithm can make a different number of comparisons.

When Sorting Is Not the Bottleneck

The expressions separate two situations. For an arbitrary edge list, sorting costs $O(m\log(m+1))$ with comparison sorting. For a list guaranteed to be sorted already, Kruskal can proceed directly to the scan, saving that cost. If someone must verify that a supplied list is sorted, checking consecutive weights takes at most $m-1$ comparisons when $m\ge1$; that check is linear and does not require sorting.

In either situation, disjoint-set initialization and edge tests remain. The DSU work is small relative to comparison sorting in many ordinary settings because $\alpha(n)$ grows extremely slowly, but the terms should not be confused: sorting orders the edges, while Find and Union track which components the accepted edges have joined. In a disconnected graph, a full scan produces a forest, not a spanning tree, and isolated vertices contribute to $n$ and to the initialization cost even though they contribute no edge tests.

Common Pitfalls

Counting a Union for every edge. Rejected edges do not merge sets, so they do not cause a Union. The six-edge example has four accepted edges and therefore four Union calls, not three and not six.

Forgetting endpoint Find calls on rejected edges. An edge must be tested before the algorithm can reject it. Under the convention used here, every scanned edge contributes two endpoint Find calls, whether it is accepted or rejected.

Dropping the initialization term. If $m=0$ but $n$ is large, there is no sorting or edge scanning, but the standard implementation still initializes one disjoint set for each vertex. A bound that omits $n$ can therefore misstate the cost on such inputs.

Using the connected-graph shorthand without its hypothesis. The simplification to $O(m\log n)$ uses $m\ge n-1$, which holds for connected graphs with $n\ge2$. A disconnected graph can have many vertices and very few edges, so keep the initialization term when describing the general case.

Check Your Understanding

Use the full-scan convention unless a question specifies otherwise.

A graph has $n=8$ vertices, $m=9$ edges and $c=3$ connected components. How many endpoint Find calls and successful Union calls does Kruskal make?
Why does a rejected edge still require Find calls?
State the running-time bound when the input edge list is already sorted and the DSU uses union by rank with path compression.
For a connected simple graph with $n\ge2$, explain why the comparison-sort bound can be written $O(m\log n)$.
What cost remains if a graph has vertices but no edges, and why?