Minimum Spanning Trees: Kruskal, Prim and the Cut Property

By the end of this lesson you will be able to say what a minimum spanning tree is, prove with the cut property (the light-edge argument) why a greedy choice is safe, trace genericMst, mstKruskal (sorted edges plus a disjoint-set forest you can watch) and mstPrim (a key/parent table plus a priority queue you can watch) step by step, compute the second-best MST, run a Borůvka phase, and implement every one of them in Dart.

0. What is a minimum spanning tree?

Read this first if any word below is new. Everything here builds on graphs and graph search, on the greedy idea from the greedy-algorithms lesson, and on disjoint sets from the disjoint-sets lesson; the priority queue Prim needs is the heap of the heapsort lesson (and the Fibonacci-heap lesson for the fast version).

Words you need.

Graph G = (V, E): a set V of dots called vertices and a set E of lines called edges, each edge joining two vertices. We use undirected edges (no arrow direction).
Weight w(u, v): a number written on an edge (a cost, a distance, a wire length).
Path: a walk along edges from one vertex to another. Connected: a path exists between every pair of vertices. Cycle: a path that ends where it started without repeating an edge.
Tree: a connected graph with no cycle. Spanning tree: a tree that uses every vertex of G and only edges of G. Minimum spanning tree (MST): a spanning tree whose total weight w(T) is as small as possible.
Greedy algorithm: builds an answer by repeatedly taking the choice that looks best right now and never undoing it. The whole lesson is about proving that here this is safe.

You are wiring electricity to n houses. Some pairs of houses can be joined by a wire, and each possible wire has a cost. You do not need a wire between every pair, only enough so everybody ends up on one network, using as little total wire as possible. A spanning tree is such a set of wires: it touches every house and has no loops (a loop means one wire could be removed and everyone would still be connected, so it was wasted). The minimum spanning tree is the cheapest such network.

Small example. A triangle with wires a-b costing 1, b-c costing 2 and a-c costing 3. A spanning tree of 3 houses needs exactly 2 wires. The three choices cost 1 + 2 = 3, 1 + 3 = 4 and 2 + 3 = 5; the cheapest (green) is the MST.

Formally: given a connected undirected graph G = (V, E) with a weight w(u, v) on every edge, find an acyclic edge set T ⊆ E connecting all vertices with minimum total weight w(T). A tree on n vertices always has exactly n − 1 edges: fewer cannot reach everyone, more must contain a cycle.

Dart: the identity “a tree on n vertices has n − 1 edges”, checked on all 64 edge subsets of K₄ (pieces = n − edges for every acyclic subset, and exactly 16 of them are spanning trees).

An MST is not necessarily unique: equal-weight edges can be swapped to give a different tree of the same total weight (the equal-weight triangle has three MSTs). What is always identical is the total weight, and even the sorted list of edge weights is the same for every MST. Also, "minimum" is about the sum of all wires, not about the shortest route between two houses (that is shortest paths, a different problem).

Why does an MST never contain a cycle when all weights are positive? If it did, deleting one edge of the cycle would keep everyone connected and lower the total. With zero or negative weights a minimum-weight connected edge set could keep a cycle, which is why the problem is stated as "spanning tree" rather than "cheapest connecting set".

An MST connects all n vertices with exactly n − 1 edges and no cycle at the smallest total weight. It may not be unique, but its weight is.

Growing a minimum spanning tree: genericMst and the cut property

The generic method

Imagine assembling a jigsaw puzzle where you may only place a piece if you can prove that some correct finished picture uses that piece there. If every piece you place is provably right, you never have to backtrack. An edge you can add to your current edge set A without ruining "A is part of some MST" is called safe.

Small example. On the triangle above, start with A = ∅. The edge a-b (cost 1) is safe: the MST contains it. So is b-c after it. The edge a-c is not safe once a-b and b-c are in A: it would close a cycle.

genericMst(G) keeps a set A that is always a subset of some MST (the loop invariant) and repeatedly adds one safe edge until A is a spanning tree.

The loop invariant works like this: Initialization: after line 1, A = ∅ trivially lies inside some MST. Maintenance: lines 2-4 only ever add safe edges, so "A is inside some MST" stays true. Termination: every edge of the final A lies in an MST and A spans, so A is itself an MST. The tricky part is line 3: how do we recognise a safe edge? That is the cut property.

A safe edge always exists. When line 3 runs, the invariant says some MST T contains A, and A is a proper subset of T (otherwise the loop would have ended). So T has an edge (u, v) ∉ A, and that edge is safe. The algorithm never gets stuck.

Cuts and light edges: the cut property

Draw a curtain across the graph splitting the vertices into two groups, S and V − S. That split is a cut. An edge with one end on each side crosses the cut. The cut respects A if no edge of A crosses it (the curtain never slices through a wire you already chose). The cheapest crossing edge is a light edge; ties give several light edges.

The cut property. Let A be a subset of some MST, let (S, V − S) be any cut that respects A, and let (u, v) be a light edge crossing it. Then (u, v) is safe for A.

Small example: the campus-cable graph. This lesson's main example has 9 buildings a–i and 14 possible cable runs: a-b:3, a-d:5, a-e:7, b-c:4, b-e:4, c-f:2, d-e:2, d-g:6, e-f:4, e-h:3, f-i:5, g-h:4, h-i:2, e-i:7 (V = 9, E = 14; its MST weighs 24). Take S = {a, b, d, e} and A = {a-b, d-e, c-f, h-i, g-h} (each edge of A stays on one side, so the cut respects A). The crossing edges are b-c:4, d-g:6, e-f:4, e-h:3 and e-i:7, so the unique light edge is (e, h) with weight 3. The cut property promises that (e, h) is safe. The four players below run the cut-and-paste proof on real cuts: watch which edges cross, which are light, and how a tree that avoids the light edge gets repaired by one swap without getting heavier.

Reading the proof off the animation. Start with a spanning tree T that contains A but not the light edge (u, v). Adding (u, v) to T creates exactly one cycle: (u, v) plus the tree path from u to v. Since u and v are on opposite sides of the cut, that path must cross the cut at some edge (x, y), and (x, y) ∉ A because the cut respects A. Swap: T′ = T − {(x, y)} ∪ {(u, v)} is again a spanning tree containing A, and w(T′) = w(T) − w(x, y) + w(u, v) ≤ w(T) because (u, v) is light. So there is an MST that contains A ∪ {(u, v)}.

The words "respects A" are not decoration. Player 3 shows a cut that slices through A: its light edge a-c closes a cycle with A, so it is not safe. Also do not confuse "a light edge of some cut" with "every light edge of every cut": in an equal-weight triangle each edge is a light edge of some cut, yet all three together contain a cycle.

The component rule. Let C be a connected component (a tree) of the forest (V, A) where A ⊆ some MST. If (u, v) is the cheapest edge leaving C, it is a light edge of the cut (V_C, V − V_C), which respects A, so (u, v) is safe. Kruskal's algorithm uses it with C = one of the trees; Prim's algorithm uses it with C = the single growing tree.

Dart: the three cut helpers. WEdge(u, v, w) is the small edge class used throughout this page; vertices are String labels, so a cut is a Set<String>.

Dart: the cut property and the component rule as an executable test on the campus graph. The helper allMsts enumerates every spanning tree (tiny graphs only), so the test checks the theorem against ground truth instead of assuming it.

A cheapest edge crossing any cut that respects your current edges is always safe. Kruskal and Prim are two different ways of choosing which cut to look at.

genericMst in action

The animations below use the component rule as the safe-edge rule: at each step they take the component whose name sorts first as S (purple), mark every edge crossing the cut (orange) and add the light edge. Watch the cut, the crossing edges and the light edge change every step.

Dart implementation of this strategy (one valid way to find a safe edge; Kruskal's below uses another). DisjointSet is defined in the next section.

Input size → what is feasible. genericMst as coded rescans all E edges for each of the V − 1 safe edges, about V·E steps. V = 1000, E = 3000 → 3·10⁶ steps, fine; V = 10⁵, E = 2·10⁵ → 2·10¹⁰, far too slow: use Kruskal or Prim.

Finding a safe edge is the whole difficulty. "Just add the cheapest remaining edge" is fine only if you also skip edges that close a cycle; that extra test is exactly what Kruskal's find comparison does.

The union-find toolbox: makeSet, find, union

Kruskal has to answer, thousands of times, the question "are these two vertices already connected by the edges chosen so far?" A disjoint-set forest (full lesson here) answers it fast. Here are exactly the three operations Kruskal calls.

Think of clubs at a school. Every club has one leader. To learn whether two students are in the same club, ask each "who is your leader?" (find) and compare the answers. To merge two clubs (union) make one leader report to the other. Each student stores only "who I report to" (the parent), and leaders report to themselves.

Small example. Elements a, b, c, d. makeSet makes four one-person clubs. union(a, b) merges the first two; union(c, d) the last two; union(b, c) merges the two pairs. Now find(a) = find(d).

Two tricks keep the trees short. Union by rank: rank is an upper bound on a tree's height; the tree with the smaller rank always hangs under the taller one (on a tie the rank of the new top grows by one). Path compression: while find walks up to the root, it re-points every node on the way straight at the root, so later finds on those nodes are one step. Together they make the total cost of m operations on n elements O(m α(n)), where α (the inverse Ackermann function) is at most 4 for any n you can ever store.

Dart implementation. parent and rank are two Maps keyed by the vertex label, so there is no array index to worry about. find is recursive. union skips the link when both roots are equal (union is only meaningful for different sets).

Dart: link as a function of its own (union(x, y) = link(find(x), find(y))), and the fact behind the speed: a root of rank r owns at least 2^r nodes, so rank ≤ ⌊lg n⌋. The code checks it on 3000 random unions and on the worst-case tournament of 1024 elements.

Input size → what is feasible. m = 10⁶ operations on n = 10⁵ elements cost about 4·10⁶ steps (α(n) ≤ 4); a naive “relabel one whole set on every union” structure could need n·m = 10¹¹ steps.

Compare roots, not parents: parent[x] == parent[y] is false for two vertices of the same tree that hang at different depths. And never call link on a root with itself: it would bump its rank for nothing (harmless for correctness, but the rank stops meaning anything useful).

Rank never exceeds ⌊lg n⌋: a root of rank r has at least 2^r nodes, because ranks grow only when two equal-rank trees are merged. So even without path compression, union by rank keeps every find at O(lg n). Path compression on top brings the amortized cost down to α(n); the full analysis is in the disjoint-sets lesson.

find(u) == find(v) means "already connected". union merges two sets by hanging the lower-ranked root under the higher-ranked one. Both are almost constant time.

Kruskal's algorithm

Sort every edge from cheapest to dearest and walk down the list. Take an edge only if its two ends are still in different groups (taking it cannot form a cycle); skip it otherwise. Each taken edge merges two groups. "Which group is each vertex in?" is answered by the disjoint-set forest from the previous section.

Small example. Vertices a, b, c, d with edges a-b:2, b-c:5, a-c:4, c-d:1, b-d:6. Sorted: c-d:1, a-b:2, a-c:4, b-c:5, b-d:6. Take c-d (sets {c,d}), take a-b (sets {a,b} {c,d}), take a-c (all four in one set). The last two edges have both ends in the same set and are skipped. Total 1 + 2 + 4 = 7.

Each frame shows the graph, the sorted edge list, and the disjoint-set forest drawn as trees, so you can see makeSet create singletons, find walk to roots (and compress paths), and union hang one root under another.

Classic bug: accepting the edge but forgetting union. Then every later edge still looks safe and the total comes out too large. See question c23-q11. Another trap: List.sort in Dart is not guaranteed stable, so equal-weight edges may come out in a different order than in this page's JavaScript; the MST weight is identical, the tree may differ.

Correctness: every accepted edge is the lightest one leaving its component at that moment (the component rule), so it is safe. Running time: makeSet costs O(V); sorting costs O(E lg E) = O(E lg V) since E < V²; the loop does 2E find and at most V − 1 union calls costing O((V + E) α(V)) in total. The sort dominates: O(E lg V). The two players below turn that into a cost table for a graph size of your choice.

Dart implementation (vertices are String labels, so makeSet / find / union map directly onto the label-keyed DisjointSet above):

Dart: Kruskal’s cost counted instead of claimed. For sparse graphs with V = 100, 1000, 10⁴ and E = 3V it counts the sort’s comparisons, the 2E find calls and the V − 1 union calls, and checks lg E < 2 lg V (why O(E lg E) = O(E lg V)).

Input size → what is feasible. E ≤ 2·10⁵ → sort ≈ 3.5·10⁶ comparisons, well under a second. E = 10⁷ → E lg E ≈ 2.3·10⁸, a few seconds and the edge list is the memory limit. A dense graph with V = 10⁵ (E ≈ 5·10⁹) cannot even be stored: use array Prim on an implicit graph (question c23-q17).

Kruskal has a hidden ingredient: line 4 puts the edges in nondecreasing order, which is what turns "lightest edge that leaves some component" into "the next edge in the list whose ends are in different components". If the weights are small integers the sort can be a counting sort, and the whole algorithm then runs in O(E α(V)) (question c23-q32).

Kruskal: sort all edges, keep an edge when its ends are in different trees, merge the trees. It needs a disjoint-set forest and costs O(E lg V), almost all of it the sort.

Prim's algorithm

Grow one single tree from a root like ink spreading from one drop. At each step take the cheapest edge leaving the tree to a vertex not yet in it. Every outside vertex remembers key (the cheapest known edge to the tree, ∞ if none) and parent (the tree vertex at the other end of that edge). A priority queue Q of outside vertices hands out the smallest key. A min-priority queue is a container that always lets you remove the smallest item quickly (see the heapsort lesson).

Small example. Same graph as before, root a. key[a] = 0. Extract a: key[b] = 2, key[c] = 4. Extract b (2): key[d] = 6. Extract c (4): key[d] becomes 1 (edge c-d is cheaper). Extract d (1). Tree edges a-b, a-c, c-d: total 7, the same weight Kruskal found.

Below, the table on the right of every frame is the key/parent array: the row of u just taken out of Q is blue, the neighbour being examined is orange, and the line Q (smallest key first) shows what the priority queue currently holds.

Line 7 (extract the smallest key) and lines 9-11 (the key decrease) are exactly the queue operations of the heapsort lesson; every Prim player below shows the queue's contents in the Q line, so each of them is also a worked example of extractMin and decreaseKey.

Line 9 has two conditions and both matter: v in Q and w(u, v) < key[v]. Forgetting the first lets a vertex that is already in the tree get a new key, which corrupts the table (question c23-q19). And Prim needs a connected graph: on a disconnected one the vertices of other components keep key ∞ (third player).

Loop invariant: before each iteration A = {(v, parent[v]) : v ∈ V − {r} − Q}; the tree vertices are exactly V − Q; for every v ∈ Q with parent[v] ≠ NIL, key[v] is the weight of the light edge (v, parent[v]) connecting v to the tree. This makes each extractMin pick a light edge of the cut (tree, rest), which respects A.

Running time. (Big-O notation is explained in the growth-of-functions lesson.) Prim's algorithm does V extractMin calls (line 7: remove the smallest item from Q) and, over the whole run, at most E decreaseKey calls (line 11: lower the key of an item already in Q). With a binary heap that is O((V + E) lg V) = O(E lg V); with a plain array (extractMin scans) O(V²); with a Fibonacci heap O(E + V lg V). Prim's resembles Dijkstra's shortest-path algorithm, but its key is the distance to the tree, not from the source. The players below compare the three queues for a graph size of your choice.

Dart implementation (key and parent are maps keyed by label and Q is a set scanned linearly for the extractMin step, which is the O(V²) variant; question c23-q26 builds the heap version):

Dart: the three Prim bounds as functions (array V², binary heap (V + E) lg V, Fibonacci heap E + V lg V), plus an instrumented Prim that counts the V extractMin calls and the decreaseKey calls (at most E), and the sparse-versus-dense comparison.

Input size → what is feasible. V ≤ 2000 dense (E ≈ 2·10⁶) → array Prim does V² = 4·10⁶ steps; V = 10⁵, E = 3·10⁵ → heap Prim costs (V + E) lg V ≈ 6.6·10⁶, while array Prim would need V² = 10¹⁰ steps, far too slow.

Kruskal: sort all edges, merge components (needs disjoint sets). Prim: grow one tree, always take the cheapest edge leaving it (needs a priority queue). Both are O(E lg V) with the right structures and both are correct because of the cut property.

Why both are correct: the loop invariant, checked

A detective proves a suspect is innocent by checking every possible scene of the crime. We do the same for the invariant "A is inside some MST": these players enumerate every spanning tree of a small graph by brute force, keep the minimum ones, and after each edge Kruskal or Prim accepts, count how many of them still contain A. The count never reaches zero.

Small example. On the triangle a-b:1, b-c:2, a-c:3 the only MST is {a-b, b-c}. Kruskal accepts a-b (1 of 1 MSTs contains it), then b-c (1 of 1), and skips a-c.

Notice what the counts tell you. On the campus graph several MSTs exist (ties), and the count shrinks as A commits to particular tie-breaks, but it never drops to 0: that is exactly "A is a subset of some MST". At the end A has n − 1 edges and is contained in a tree with n − 1 edges, so it is that tree.

Dart: the loop invariant as a function (true after every accepted edge of Kruskal on the campus graph, starting from A = ∅) and the claim “a safe edge always exists while A is not yet an MST”.

The brute-force check proves nothing by itself for large graphs (it only samples small ones); the proof is the cut property. The animation just lets you see the theorem hold on real examples.

A different way to see why greedy works: the acyclic edge sets (forests) of a graph form a graphic matroid, and greedy algorithms are optimal on matroids (see the greedy-algorithms lesson).

Kruskal's and Prim's differ only in which cut they look at; each edge they take is a light edge of a cut that respects the edges taken so far, so the invariant "A ⊆ some MST" survives every step.

Second-best minimum spanning tree

Your cheapest cable network is built, but one cable is unavailable today. What is the cheapest alternative network? A second-best MST is the cheapest spanning tree that is not the MST itself: among all spanning trees except the chosen MST, the one of least weight.

Small example. Triangle a-b:1, b-c:2, a-c:3. The MST is {a-b, b-c} (3). The only other spanning trees are {a-b, a-c} (4) and {b-c, a-c} (5), so the second-best weight is 4: swap b-c for a-c.

Four facts lead to the algorithm: (a) with distinct weights the MST is unique but the second-best need not be; (b) a second-best tree differs from the MST T by exactly one swap T − {(u, v)} ∪ {(x, y)} with (u, v) ∈ T, (x, y) ∉ T; (c) you can compute maxEdge[u][v], the heaviest edge on the tree path between every pair, in O(V²) by searching the tree from each vertex; (d) try every non-tree edge (x, y) with cost w(T) − maxEdge[x][y] + w(x, y) and take the smallest.

Two traps. First, with distinct weights the second-best tree is strictly heavier than the MST, but with ties (the campus graph has several) it can weigh exactly the same, and the third player shows it. Second, if G is itself a tree there is nothing to swap and no second-best exists, so the Dart function returns null.

Why one swap suffices. Let T′ be any spanning tree other than the MST T, and let k be the number of edges of T′ that are not in T (so T has k edges not in T′). A standard fact about spanning trees (the exchange property of matroids) lets you pair the k new edges f of T′ with the k old edges g of T so that every single swap T − {g} ∪ {f} is a spanning tree. Each swap costs w(f) − w(g) ≥ 0 because T is minimum, and w(T′) − w(T) is the sum of all k swap costs. The cheapest single swap therefore costs at most that sum, so it gives a tree that is different from T and no heavier than T′. Hence the second-best weight is the cheapest single swap. The table maxEdge[u][v] makes each swap cost O(1) to price; filling it costs V searches of O(V), so after the MST the whole algorithm is O(V² + E).

Dart implementation (vertices are labels; maxEdge is a map of maps instead of a 2-D array):

Input size → what is feasible. V ≤ 2000, E ≤ 2·10⁵ → the max table has V² = 4·10⁶ entries (32 MB) plus an E lg E ≈ 3.5·10⁶ sort; V = 10⁵ would need a 10¹⁰-entry table, so a path-maximum structure such as binary lifting (O(E lg V)) is required there.

Second-best MST = best single swap. Price every swap (x, y) ∉ T as w(T) − maxEdge[x][y] + w(x, y) using the tree-path maximum table, in O(V²) total after the MST.

A Borůvka phase: contracting the graph

Every town on a map quietly asks for its cheapest road to any neighbour; all those roads are certainly worth building (each is the lightest edge leaving a single town). Then each cluster of joined towns is treated as one big town and the map is redrawn with far fewer towns. Repeat, and the map collapses quickly to a single town.

Small example. Path a-b:1, b-c:2, c-d:3. a picks a-b. b is already used. c picks its cheapest edge b-c (2) and d picks c-d (3): everything merged in one phase, so the contracted graph is a single vertex.

For a very sparse graph, Prim with Fibonacci heaps can be beaten by first shrinking the graph. boruvkaPhase(G, T) chooses, for every still-unmarked vertex u, its lightest incident edge, puts the original edge into T, unions the two endpoints, then builds the contracted graph H with one vertex per set and, for parallel edges, only the lightest one. Every vertex is merged with at least one other, so |H.V| ≤ |V|/2; each phase costs O(E) with simple data structures, and running k = lg lg V phases followed by mstPrim gives O(E lg lg V). Repeating phases O(lg V) times until one vertex is left is Borůvka's algorithm (1926).

Dart implementation (a CEdge is a WEdge that remembers the orig edge of the input graph, and a Dart 3 record returns the contracted graph's vertices and edges together):

Dart: one phase at least halves the number of vertices, and T plus the MST of the contracted graph is an MST of G; the code checks both on 100 seeded random graphs.

Input size → what is feasible. this page’s code scans all E edges for every vertex (V·E): fine for V ≤ 1000, E ≤ 5000 (5·10⁶ steps). A real phase is O(E), so ⌈lg V⌉ phases cost O(E lg V).

Line 5's marked test is what stops two vertices choosing the same edge twice and what makes the unions cycle-free: an unmarked vertex is always still a singleton, so union(u, v) always merges two different sets. Skipping the marked test would double-count edges.

Why is every chosen edge safe? The lightest edge at a vertex u is a light edge of the cut ({u}, V − {u}). Choosing many at once is still safe (with distinct weights they are all in the unique MST; the Dart test also checks graphs with ties). This page's check reports that T plus the MST of the contracted graph has exactly the MST weight of G.

One Borůvka phase picks each vertex's cheapest edge, then contracts: the vertex count at least halves in O(E) time.

Bottleneck trees and three more strategies

Bottleneck spanning tree

A road network is limited by its weakest bridge. A bottleneck spanning tree minimizes the weight of the heaviest edge used (its "value"). Every MST is a bottleneck spanning tree, so an MST algorithm already solves it. A linear-time test for "is there a spanning tree whose edges all weigh at most b?" is in question c23-q41, and c23-q33 uses the idea for minimax paths.

Small example. Triangle a-b:1, b-c:2, a-c:3. The MST {a-b, b-c} has heaviest edge 2, and no spanning tree can do better (any spanning tree needs two edges of the triangle, and the two lightest have max 2).

Why an MST is a bottleneck tree: if some spanning tree had a smaller heaviest edge M, all its edges weigh less than the MST's heaviest edge m; deleting m from the MST splits it into two parts, and a lighter tree must have an edge crossing that cut with weight less than m; swapping it in would make a lighter MST, a contradiction.

The converse is false: a bottleneck spanning tree is not necessarily an MST. Its heaviest edge is as small as possible, but the other edges may be needlessly heavy. Also, the bottleneck value depends only on the single heaviest edge, so many different trees can share it.

Dart: the value of a spanning tree is its heaviest edge. The code takes the minimum over all spanning trees of the campus graph, shows the MST attains it, and gives a tiny counterexample to the converse.

Every MST is a bottleneck spanning tree, so an MST algorithm solves this problem too; the "weakest link" (minimax) path between two vertices is the path inside the MST.

Three more strategies: which of them really give an MST?

Here are three short procedures that look plausible. The animations below run each on real inputs; the verdicts are: reverseDelete is correct, anyOrderSkipCycles is not, addAndEvict is correct.

reverseDelete: start with all the roads and repeatedly close the most expensive road you can spare (one that has a detour). anyOrderSkipCycles: build roads in whatever order they arrive and skip only the ones that would make a loop. addAndEvict: build roads as they arrive, and whenever a loop appears, close the most expensive road of that loop.

reverseDelete (heaviest first, keep connected)

Small example. Triangle with weights 3, 2, 1 (c-a:3, b-c:2, a-b:1). Nonincreasing order: 3, 2, 1. Removing 3 keeps things connected: remove. Removing 2 would disconnect: keep. 1 also kept. Result weight 3 = the MST.

Correct, because an edge is only removed when it is (one of) the heaviest on a cycle, and such an edge belongs to no MST (the cycle property below). As written, each connectivity test costs O(V + E), so it runs in O(E (V + E)) plus the sort; it is the slowest of the three.

Input size → what is feasible. as written O(E (V + E)): V = 500, E = 2000 → 5·10⁶ steps, fine; V = 10⁵, E = 2·10⁵ → 6·10¹⁰, too slow.

anyOrderSkipCycles (arbitrary order, skip cycles)

Small example. Same triangle in the order 3, 2, 1: it keeps 3 and 2 (weight 5) and skips 1 because it would close a loop, but the MST weighs 3. It only guarantees a spanning tree.

Not necessarily an MST, since it never looks at weights. Fed the edges in nondecreasing order it is Kruskal. Its best implementation is the same disjoint-set forest: O(E α(V)) if the edges come pre-sorted, and it never exceeds that for a fixed order.

Input size → what is feasible. with the disjoint-set forest, E = 2·10⁵ edges in any order → about E·α(V) ≈ 10⁶ steps, but remember the result is only a spanning tree.

addAndEvict (arbitrary order, repair cycles)

Small example. Order a-b:1, b-c:2, a-c:5: the third edge closes a cycle whose heaviest edge is the new one itself, so it is dropped immediately.

Correct: at every moment T is a minimum spanning forest of the edges seen so far, because each removed edge is the heaviest on a cycle. Finding the cycle by a search of the current tree costs O(V) per edge, so O(E V) as written; smarter dynamic-tree structures do better.

Input size → what is feasible. O(E·V): V = 1000, E = 5000 → 5·10⁶ steps; V = 10⁵, E = 2·10⁵ → 2·10¹⁰, too slow: use Kruskal when all edges are known upfront.

Dart: the cycle property as a test. An edge e = (u, v) is a heaviest edge of some cycle exactly when the other edges of weight ≤ w(e) already connect u and v; the code checks that some MST avoids every such edge.

The cycle property behind reverseDelete and addAndEvict. If e is a maximum-weight edge on some cycle of G, some MST of G avoids e: take an MST that uses e, delete e to split it in two, and let another edge e′ of the cycle reconnect the halves; then w(e′) ≤ w(e), so the new tree is no heavier. reverseDelete deletes only such edges. addAndEvict keeps, after every edge, a minimum spanning forest of the edges seen so far, because each step is one application of this property. anyOrderSkipCycles never uses it: it can permanently keep an edge that is the heaviest on a cycle it does not yet know about.

Do not conclude "any greedy that keeps the light edges works". anyOrderSkipCycles skips cycle edges but ignores weights, so it is only a spanning tree; reverseDelete and addAndEvict are right because each edge they discard is provably the heaviest on a cycle.

reverseDelete (heaviest first, keep connected) and addAndEvict (add, then evict the heaviest edge on a cycle) are correct; anyOrderSkipCycles (arbitrary order, skip cycles) is only guaranteed to be a spanning tree. The first and the last rest on the cycle property.

Quiz

Interview questions

Cheat sheet

Algorithm / procedure	Time	Space	Data structure	Use when
genericMst	depends on the safe-edge strategy (best/avg/worst all set by it)	O(V)	any safe-edge test	Understanding why greedy works
Light edge of a cut (scan crossing edges)	Θ(E) best/avg/worst	O(1) extra	edge list + set S	Proving or testing safe edges
makeSet / find / union	O(1) / O(α(n)) amortized / O(α(n)) amortized	O(n)	Disjoint-set forest (rank + path compression)	Connectivity while edges arrive
mstKruskal	O(E lg V) best/avg/worst (sort dominates; O(E α(V)) if weights are small integers)	O(V + E)	Disjoint-set forest	Sparse graphs, edge list given
mstPrim (array)	O(V²)	O(V)	Array scan	Dense graphs (E ≈ V²)
mstPrim (binary heap)	O((V+E) lg V)	O(V + E)	Binary min-heap	General purpose, sparse graphs
mstPrim (Fibonacci heap)	O(E + V lg V) amortized	O(V + E)	Fibonacci heap	Very dense graphs, in theory
secondBestMst	O(V² + E lg E): MST, then O(V²) max table, then O(E) swaps	O(V²)	maxEdge[u][v] table	Backup network, fault tolerance
boruvkaPhase (one phase)	O(E)	O(V + E)	Disjoint sets, contracted graph	Sparse graphs; Borůvka repeats it O(lg V) times
Bottleneck spanning tree	O(E) with the median trick; O(E lg V) via any MST	O(V + E)	MST or contraction	Minimax paths (weakest link)
reverseDelete	O(E lg E + E(V + E)) as written	O(V + E)	Connectivity test per edge	Correct but slow; good for teaching the cycle property
anyOrderSkipCycles	O(E α(V)) (edges given)	O(V)	Disjoint-set forest	Not an MST algorithm (any spanning tree)
addAndEvict	O(E V) as written	O(V + E)	Tree path search	Correct online (edges may arrive in any order)