47.04.06 · theoretical-cs / 04-algorithms-analysis

Minimum Spanning Trees: Kruskal's and Prim's Algorithms

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Cormen, Leiserson, Rivest, and Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 19 and Ch. 21 (Kruskal, Prim, Boruvka, the role of the cut property, Fibonacci heap speedup for Prim giving $O (E + V lo g V)$ , and the Tarjan Cheriyan survey of MST algorithms)

Intuition Beginner

Imagine you are building a road network connecting several towns. You want every town reachable from every other town, and you want to minimise total road length. The roads form a tree (no cycles needed — any cycle would mean a redundant road you could remove). This is the minimum spanning tree problem.

Two natural greedy strategies solve it. The first, due to Kruskal, sorts all roads from shortest to longest and builds the network by adding each road if it connects two previously disconnected groups. The second, due to Prim, starts from one town and repeatedly adds the shortest road connecting an already-connected town to a not-yet-connected town.

Both strategies work, and the reason is a simple property: at every step, the shortest road connecting the "already built" part to the "not yet built" part must be in the optimal network. If it were not, you could swap it in and swap a longer road out, reducing the total length. This cut property is the key to everything.

Visual Beginner

A small graph with edge weights, showing how Kruskal and Prim build the MST.

    A ---2--- B ---3--- C
    |         |         |
    4         1         5
    |         |         |
    D ---6--- E ---7--- F

Kruskal processes edges in order of weight: DE(1), AB(2), BE(3), AD(4), CF(5), DE-already-connected(6), EF(7). The MST has edges {DE, AB, BE, AD, CF} with total weight $1 + 2 + 3 + 4 + 5 = 15$ .

Prim starting from A: AB(2), then BE(1, from B), then AD(4, from A or D), then DE(1, connecting D to E... but D already connected via A-AD and E via B-BE, so skip). The tree grows: A-B, B-E, A-D, B-C, C-F.

step	Kruskal adds	weight	Prim adds	weight
1	DE	1	AB	2
2	AB	2	BE	1
3	BE	3	AD	4
4	AD	4	BC	3
5	BC	3	CF	5
6	CF	5	done

Worked example Beginner

Consider a graph with 4 vertices and 5 edges: $V = {a, b, c, d}$ with edges $ab = 4$ , $a c = 2$ , $a d = 5$ , $b c = 3$ , $c d = 1$ .

Kruskal sorts edges by weight: $c d (1)$ , $a c (2)$ , $b c (3)$ , $ab (4)$ , $a d (5)$ . Process each:

Add $c d$ (weight 1). Components: ${a}, {b}, {c, d}$ .
Add $a c$ (weight 2). Connects ${a}$ and ${c, d}$ . Components: ${a, c, d}, {b}$ .
Add $b c$ (weight 3). Connects ${b}$ and ${a, c, d}$ . All connected. Stop.

MST edges: $c d, a c, b c$ . Total weight: $1 + 2 + 3 = 6$ .

Prim starting from $a$ : the lightest edge from ${a}$ is $a c$ (weight 2). Add it. From ${a, c}$ , the lightest edges are $c d$ (weight 1) and $b c$ (weight 3). Pick $c d$ . From ${a, c, d}$ , the lightest unused edge to ${b}$ is $b c$ (weight 3). Add it. MST edges: $a c, c d, b c$ . Total weight: $2 + 1 + 3 = 6$ . Same tree.

Check your understanding Beginner

Formal definition Intermediate+

Let $G = (V, E)$ be a connected undirected graph with edge weight function $w : E \to R$ . A spanning tree of $G$ is a subgraph $T = (V, E_{T})$ that is a tree (connected and acyclic) with $E_{T} \subseteq E$ . A minimum spanning tree (MST) is a spanning tree minimising $w (T) = \sum_{e \in E_{T}} w (e)$ .

A cut of $G$ is a partition $(S, V ∖ S)$ of the vertex set. An edge crosses the cut if one endpoint is in $S$ and the other in $V ∖ S$ .

Cut property: For any cut $(S, V ∖ S)$ , the minimum-weight edge crossing the cut belongs to some MST of $G$ .

Cycle property: For any cycle $C$ in $G$ , the maximum-weight edge on $C$ does not belong to any MST of $G$ .

These two properties are the foundation of all MST algorithms ^{[CLRS Ch. 19]}. The cut property guarantees that certain edges must be in an MST (light edges crossing cuts), and the cycle property guarantees that certain edges cannot be in any MST (heavy edges on cycles).

Counterexamples to common slips Intermediate+

"The MST always includes the globally minimum-weight edge." It does. The cut $(S, V ∖ S) = ({u}, V ∖ {u})$ where $u$ is an endpoint of the minimum-weight edge $e$ has $e$ as its lightest crossing edge, so $e$ is in some MST by the cut property.
"Kruskal and Prim always produce the same MST." They always produce a minimum spanning tree, but if edge weights are not all distinct, they may produce different MSTs. Both will be minimum-weight.
"Prim's algorithm requires a specific starting vertex to work correctly." Any starting vertex works. The cut property applies at every step regardless of where the tree started growing.

Key theorem with proof Intermediate+

Theorem (correctness of Kruskal and Prim). Both Kruskal's algorithm and Prim's algorithm produce a minimum spanning tree.

Proof (via the cut property). Kruskal: process edges in order of increasing weight. When Kruskal adds edge $e = (u, v)$ , let $S$ be the connected component containing $u$ at that moment. Then $v \in / S$ (otherwise $e$ would create a cycle and be skipped). The edge $e$ is the lightest edge crossing the cut $(S, V ∖ S)$ , because all lighter edges have already been processed and either added (in which case $u$ and $v$ would already be connected) or skipped (because their endpoints were already connected). By the cut property, $e$ is in some MST. Since Kruskal adds exactly $∣ V ∣ - 1$ edges without creating cycles, the result is a spanning tree, and every edge in it is in some MST.

Prim: at each step, Prim adds the lightest edge $e = (u, v)$ where $u$ is in the current tree $T$ and $v$ is not. The cut $(V_{T}, V ∖ V_{T})$ separates the tree vertices from the rest. The edge $e$ is the lightest edge crossing this cut (by Prim's selection rule). By the cut property, $e$ is in some MST. By induction, every edge Prim adds is in some MST, and the result is a spanning tree. $□$

Running times. Kruskal with union-find (path compression + union by rank): sorting takes $O (E lo g E)$ , and $E$ union-find operations take $O (E \cdot α (V))$ where $α$ is the inverse Ackermann function. Total: $O (E lo g V)$ since $lo g E \leq 2 lo g V$ for simple graphs and $α (V) = O (1)$ .

Prim with binary heap: each of the $O (V)$ extract-min operations takes $O (lo g V)$ , and each of the $O (E)$ decrease-key operations takes $O (lo g V)$ . Total: $O (E lo g V)$ .

Prim with Fibonacci heap: extract-min takes $O (lo g V)$ amortised and decrease-key takes $O (1)$ amortised. Total: $O (E + V lo g V)$ .

Bridge. This theorem is the foundational reason greedy algorithms work for MST: the cut property guarantees that local optimality (picking the lightest crossing edge) leads to global optimality, and this is exactly the structural insight that distinguishes MST from harder optimisation problems like TSP where greedy fails. The union-find data structure in Kruskal builds toward the network flow algorithms in 47.04.03 where connectivity management is equally central, and it appears again in the analysis of approximation algorithms 47.04.08 where the MST serves as a lower bound for the TSP tour. The central insight is that the matroid structure of spanning trees makes greedy optimal — the independent sets (forests) form a matroid, and the greedy algorithm is optimal for any matroid. Putting these together, the cut property and cycle property are the two faces of this matroid structure: the cut property says adding the minimum-weight independent element is safe, and the cycle property says removing the maximum-weight dependent element is safe.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the cut property: for any cut $(S, V ∖ S)$ , the minimum-weight edge $e$ crossing the cut belongs to some MST.

Hint

Take any MST $T$ . If $e \in T$ , done. If $e \in / T$ , adding $e$ creates a cycle, and some edge $f$ on that cycle also crosses the cut. Swap $e$ for $f$ .

Answer

Let $T$ be any MST and $e = (u, v)$ be the minimum-weight edge crossing cut $(S, V ∖ S)$ with $u \in S, v \in / S$ . If $e \in T$ , done. If $e \in / T$ , add $e$ to $T$ , creating a cycle. This cycle must contain another edge $f$ crossing the cut (since the cycle enters $S$ at some point and must leave it). We have $w (e) \leq w (f)$ since $e$ is the minimum-weight crossing edge. The tree $T^{'} = T - f + e$ is a spanning tree with $w (T^{'}) = w (T) - w (f) + w (e) \leq w (T)$ . Since $T$ is minimum, $w (T^{'}) = w (T)$ , so $T^{'}$ is also an MST containing $e$ . Rubric: full credit for the exchange argument.

Exercise 4 (medium, symbolic).

Prove the cycle property: for any cycle $C$ in $G$ , the maximum-weight edge $e$ on $C$ does not belong to any MST.

Hint

If $e$ were in an MST, removing it would disconnect the tree into two parts. Some other edge of $C$ crosses the resulting cut and is lighter.

Answer

Suppose for contradiction that $e$ is the heaviest edge on cycle $C$ and $e \in T$ for some MST $T$ . Remove $e$ from $T$ , disconnecting $T$ into two components $(S, V ∖ S)$ . Since $C$ is a cycle containing $e$ , some other edge $f$ of $C$ must also cross the cut $(S, V ∖ S)$ (the cycle provides an alternative path between the endpoints of $e$ ). We have $w (f) < w (e)$ since $e$ is the heaviest. The tree $T^{'} = T - e + f$ is a spanning tree with $w (T^{'}) = w (T) - w (e) + w (f) < w (T)$ , contradicting the minimality of $T$ . Hence $e$ is not in any MST. Rubric: full credit for the exchange argument and the weight comparison.

Exercise 5 (medium, symbolic).

Trace Kruskal's algorithm on the graph with $V = {1, 2, 3, 4, 5}$ and edges: $(1, 2, w = 3)$ , $(1, 3, w = 5)$ , $(2, 3, w = 4)$ , $(2, 4, w = 7)$ , $(3, 4, w = 2)$ , $(3, 5, w = 6)$ , $(4, 5, w = 1)$ . Give the MST edges and total weight.

Hint

Sort edges by weight and add each that does not create a cycle.

Answer

Sorted edges: $(4, 5, 1)$ , $(3, 4, 2)$ , $(1, 2, 3)$ , $(2, 3, 4)$ , $(1, 3, 5)$ , $(3, 5, 6)$ , $(2, 4, 7)$ .

Add $(4, 5, 1)$ : components ${1}, {2}, {3}, {4, 5}$ .
Add $(3, 4, 2)$ : connects 3 and 4. Components ${1}, {2}, {3, 4, 5}$ .
Add $(1, 2, 3)$ : connects 1 and 2. Components ${1, 2}, {3, 4, 5}$ .
Skip $(2, 3, 4)$ : both 2 and 3 are in different components, but wait — 2 is in ${1, 2}$ and 3 is in ${3, 4, 5}$ , so adding $(2, 3)$ would connect them. Add it. Components ${1, 2, 3, 4, 5}$ .

MST edges: $(4, 5, 1), (3, 4, 2), (1, 2, 3), (2, 3, 4)$ . Total weight: $1 + 2 + 3 + 4 = 10$ .

Wait, $(1, 2, 3)$ and $(2, 3, 4)$ — adding $(2, 3)$ would connect ${1, 2}$ and ${3, 4, 5}$ , yes. 4 edges for 5 vertices. Total weight 10. Rubric: full credit for correct edge ordering and component tracking.

Exercise 6 (hard, symbolic).

Prove that spanning trees form a matroid: the independent sets are the forests (acyclic subgraphs) of $G$ , and for any forest $A$ and larger forest $B$ with $∣ B ∣ > ∣ A ∣$ , there exists $e \in B ∖ A$ such that $A \cup {e}$ is a forest.

Hint

Use the fact that a forest on $n$ vertices with $k$ connected components has exactly $n - k$ edges. Adding an edge between two components does not create a cycle.

Answer

The hereditary property holds because subsets of forests are forests. For the exchange property: let $A$ be a forest with $k_{A}$ components and $B$ be a forest with $k_{B}$ components on $n$ vertices. Then $∣ A ∣ = n - k_{A}$ and $∣ B ∣ = n - k_{B}$ . Since $∣ B ∣ > ∣ A ∣$ , we have $k_{B} < k_{A}$ , so $B$ has fewer components. There must exist an edge $e \in B$ connecting two vertices that are in the same component of $B$ but in different components of $A$ (since $B$ is more connected). Adding this $e$ to $A$ does not create a cycle (it connects two different components of $A$ ), so $A \cup {e}$ is a forest. Hence forests form a matroid. Rubric: full credit for the component-counting argument and the exchange step.

Exercise 7 (hard, symbolic).

Analyse the amortised cost of the union-find operations in Kruskal's algorithm with path compression and union by rank. Show that the total cost of $m$ operations on $n$ elements is $O (m \cdot α (n))$ where $α$ is the inverse Ackermann function.

Hint

Use the potential function argument or the iterative compression bound. Each find operation with path compression reduces the depth of all traversed nodes to at most 2.

Answer

The analysis uses the rank and level grouping of Tarjan. Each node has a rank (initially 0, increases on union). Define $level (x) = max {k : rank (x) \geq A_{k} (1)}$ where $A_{k}$ is the $k$ -th row of the Ackermann function. Since ranks are bounded by $O (lo g n)$ and $A_{k}$ grows very fast, levels are bounded by $O (α (n))$ .

A find operation traverses a path from $x$ to the root. Each non-root node $y$ on the path has $rank (parent (y)) > rank (y)$ after path compression (or at least the parent changes to a higher-rank node). The number of times a node's parent changes rank group is at most $O (α (n))$ , since moving to a higher level requires rank growth exceeding an Ackermann function value.

Total: $m$ find operations each traverse $O (α (n))$ "active" nodes (nodes whose parent changes), plus $O (1)$ work per node that stays in the same group. The total is $O (m \cdot α (n))$ . Since $α (n) \leq 4$ for all practical $n$ , this is effectively linear. Rubric: full credit for the level-grouping or potential function argument.

Exercise 8 (hard, symbolic).

Prove that Prim's algorithm with a Fibonacci heap runs in $O (E + V lo g V)$ time.

Hint

Analyse each Fibonacci heap operation: extract-min takes $O (lo g V)$ amortised, decrease-key takes $O (1)$ amortised. Count the number of each operation type.

Answer

Prim performs exactly $V - 1$ extract-min operations (one per vertex added to the tree) and at most $E$ decrease-key operations (one per edge, when a vertex's key is updated). The Fibonacci heap guarantees: extract-min in $O (lo g n)$ amortised time and decrease-key in $O (1)$ amortised time. Total: $(V - 1) \cdot O (lo g V) + E \cdot O (1) = O (V lo g V + E)$ . The initialisation (building the heap) takes $O (V)$ time. Grand total: $O (E + V lo g V)$ . This improves over the binary heap bound of $O (E lo g V)$ when the graph is dense ( $E = Ω (V lo g V)$ ). Rubric: full credit for the operation count and the amortised analysis.

Advanced results Master

Beyond the basic algorithms, MST theory includes the Boruvka algorithm, linear-time special cases, and deep connections to matroid theory.

Theorem 1 (Boruvka's algorithm). Boruvka's algorithm processes all vertices simultaneously: in each phase, every component adds its lightest outgoing edge. Each phase at least halves the number of components, so $O (lo g V)$ phases suffice. Each phase takes $O (E)$ time. Total: $O (E lo g V)$ . The advantage is natural parallelism — each component's lightest edge can be found independently ^{[CLRS Ch. 19]}.

Theorem 2 (linear-time MST for integer weights). When edge weights are integers in a bounded range, MST can be computed in $O (E)$ time using a combination of Boruvka phases and radix sort. More generally, the MST can be found in $O (E \cdot α (E, V))$ time using the Fredman-Tarjan algorithm, which is effectively linear for all practical inputs.

Theorem 3 (MST and the matroid intersection). The spanning trees of a graph form a graphic matroid: the independent sets are the forests, and the weight function defines a linear objective. The greedy algorithm is optimal for any matroid, which is why Kruskal works. The matroid perspective explains why MST is "easy" while Steiner tree (finding a minimum-weight tree spanning a subset of vertices) is NP-hard: Steiner tree is not a matroid optimisation problem.

Theorem 4 (sensitivity analysis). Given an MST $T$ and an edge $e = (u, v) \in T$ , define the replacement weight $w_{e}^{*}$ as the minimum weight of any edge that can replace $e$ in $T$ without losing the spanning property. Then $T$ remains an MST as long as $w (e)$ does not increase beyond $w_{e}^{*}$ . Computing all replacement weights takes $O (E)$ time using the max-edge-weight queries on the MST, which connects to the lowest common ancestor data structure.

Theorem 5 (MST verification). Given a spanning tree $T$ , verifying whether $T$ is an MST can be done in $O (E)$ time, without knowing whether $T$ came from any particular algorithm. The algorithm checks that for every non-tree edge $e$ , the maximum-weight edge on the path in $T$ between the endpoints of $e$ has weight $\leq w (e)$ . If this holds for all non-tree edges, $T$ is minimum, by the cycle property.

Synthesis. The foundational reason MST has such efficient algorithms is the matroid structure of spanning trees: the cut property and cycle property together guarantee that greedy is optimal, and this is exactly the structural condition that separates MST from NP-hard problems like Steiner tree where the matroid property breaks down. The union-find data structure in Kruskal builds toward the more advanced connectivity data structures used in dynamic graph algorithms, and the Fibonacci heap speedup for Prim appears again in shortest-path algorithms where the same decrease-key-heavy access pattern dominates. The central insight is that the cut property provides a local optimality condition — each edge added is the best choice for its cut — and putting these together, every step of Kruskal and Prim is independently justified without needing to look ahead. The bridge is that the matroid greedy theorem generalises beyond MST to any problem where the feasible solutions form a matroid, and this is dual to the greedy algorithms for scheduling and Huffman coding covered in 47.04.01, where similar exchange arguments justify local optimality.

Full proof set Master

Proposition 1 (cut property). For any cut $(S, V ∖ S)$ of $G$ , the minimum-weight edge crossing the cut belongs to some MST.

Proof. Let $e$ be the lightest crossing edge. Let $T$ be any MST. If $e \in T$ , done. Otherwise, $T \cup {e}$ contains a cycle $C$ . Some edge $f \neq = e$ of $C$ also crosses the cut. Since $w (e) \leq w (f)$ , the tree $T^{'} = T - f + e$ satisfies $w (T^{'}) \leq w (T)$ , so $T^{'}$ is an MST containing $e$ . $□$

Proposition 2 (cycle property). For any cycle $C$ , the maximum-weight edge on $C$ is in no MST.

Proof. Let $e$ be the heaviest edge on $C$ . Suppose $e \in T$ for MST $T$ . Removing $e$ disconnects $T$ into components $(S, V ∖ S)$ . Some other edge $f$ of $C$ crosses this cut. Then $T^{'} = T - e + f$ has $w (T^{'}) < w (T)$ , contradicting minimality. $□$

Proposition 3 (Kruskal correctness). Kruskal's algorithm produces an MST.

Proof. Process edges in increasing weight order. When edge $e$ is added, let $S$ be the component containing one endpoint. Edge $e$ is the lightest edge crossing the cut $(S, V ∖ S)$ , since all lighter edges were already processed (and either added to connect these components or skipped because the components were already connected). By the cut property, $e$ is in some MST. After adding $∣ V ∣ - 1$ edges, the result is a spanning tree. $□$

Proposition 4 (Prim correctness). Prim's algorithm produces an MST.

Proof. At each step, let $S$ be the set of tree vertices. Prim adds the lightest edge crossing $(S, V ∖ S)$ . By the cut property, this edge is in some MST. By induction, every added edge is in some MST, and the result after $∣ V ∣ - 1$ steps is a spanning tree. $□$

Proposition 5 (running time of Prim with Fibonacci heap). Prim with a Fibonacci heap runs in $O (E + V lo g V)$ .

Proof. Each vertex is extracted once: $V$ extract-min operations at $O (lo g V)$ amortised each. Each edge causes at most one decrease-key: $E$ operations at $O (1)$ amortised each. Initialisation: $O (V)$ . Total: $O (V lo g V + E)$ . $□$

Connections Master

Amortized analysis 47.04.01 provides the tools for analysing the union-find data structure in Kruskal and the Fibonacci heap in Prim. The path-compression analysis of union-find is a foundational amortised analysis.
Graph theory 40.04.01 supplies the definitions of trees, cuts, and cycles that underpin the cut and cycle properties. The exchange arguments in the proofs are graph-theoretic at their core.
Network flow 47.04.03 extends the connectivity management ideas from MST to the more complex max-flow setting, where the cut property becomes the max-flow min-cut theorem.
Approximation algorithms 47.04.08 use the MST as a lower bound for the TSP tour: the TSP tour minus one edge is a spanning tree, so $w (MST) \leq w (TSP)$ . This gives the 2-approximation for metric TSP.

Historical & philosophical context Master

The MST problem has a rich history spanning multiple independent discoveries. Otakar Boruvka formulated and solved the problem in 1926 for the electrification of Moravia, making it one of the earliest combinatorial optimisation problems. Joseph Kruskal published his algorithm in 1956 in "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem" (Proceedings of the AMS). Robert Prim published his algorithm in 1957, though it had been independently discovered by Vojtech Jarnik in 1930 ^{[CLRS Ch. 19]}.

The matroid connection was recognised in the 1960s, when it became clear that the greedy algorithm's success for MST was not accidental but reflected a deep algebraic structure. The development of efficient union-find data structures by Tarjan and van Leeuwen in the 1970s gave Kruskal's algorithm its modern $O (E \cdot α (V))$ union-find cost.

Bibliography Master

@article{kruskal1956shortest,
  author  = {Kruskal, Joseph B.},
  title   = {On the shortest spanning subtree of a graph and the traveling salesman problem},
  journal = {Proceedings of the American Mathematical Society},
  volume  = {7},
  number  = {1},
  year    = {1956},
  pages   = {48--50}
}

@article{prim1957shortest,
  author  = {Prim, Robert C.},
  title   = {Shortest connection networks and some generalizations},
  journal = {Bell System Technical Journal},
  volume  = {36},
  number  = {6},
  year    = {1957},
  pages   = {1389--1401}
}

@article{boruvka1926ojistem,
  author  = {Bor\r{u}vka, Otakar},
  title   = {O jist\'{e}m probl\'{e}mu minim\'{a}ln\'{i}m},
  journal = {Pr\'{a}ce Moravsk\'{e} P\v{r}\'{i}rodov\v{e}deck\'{e} Spole\v{c}nosti},
  volume  = {3},
  year    = {1926},
  pages   = {37--58}
}

@book{cormen2022introduction,
  author    = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
  title     = {Introduction to Algorithms},
  publisher = {MIT Press},
  edition   = {4th},
  year      = {2022}
}

Prerequisites

47.04.01 pending
40.04.01 pending

Tier anchors

beginner: Cormen, Leiserson, Rivest, and Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 19 (the idea of a spanning tree that minimises total edge weight, and two greedy strategies for building one)
intermediate: Cormen, Leiserson, Rivest, and Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 19 (Kruskal's algorithm with union-find, Prim's algorithm with priority queues, the cut property, and the cycle property, with correctness proofs and running-time analyses)
master: Cormen, Leiserson, Rivest, and Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 19 and Ch. 21 (Kruskal, Prim, Boruvka, the role of the cut property, Fibonacci heap speedup for Prim giving $O (E + V lo g V)$ , and the Tarjan Cheriyan survey of MST algorithms)

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. — Introduction to Algorithms · MIT Press, 4th edition (2022). Ch. 19 develops minimum spanning trees: §19.1 defines the MST problem for a connected undirected graph $G = (V, E)$ with edge weight function $w : E \to R$ , proves the cut property (the minimum-weight edge crossing any cut of $V$ belongs to some MST) and the cycle property (the maximum-weight edge on any cycle is not in any MST); §19.2 presents Kruskal's algorithm that sorts edges by weight and adds each edge that connects two different components, maintained by a union-find data structure with path compression and union by rank giving $O (E l o g V)$ time; §19.2 also presents Prim's algorithm that grows a single tree from a root vertex, always adding the minimum-weight edge connecting the tree to a non-tree vertex, implemented with a binary heap giving $O (E l o g V)$ or a Fibonacci heap giving $O (E + V l o g V)$ ; correctness of both algorithms follows from the cut property by showing that each added edge is the minimum-weight edge across the cut separating the chosen and unchosen vertices.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m