221: Minimum Spanning Trees: Kruskal, Prim, Cut Property, and Use Cases

Learning outcomes

By the end of this lesson, you can:

explain and apply a spanning tree in a realistic implementation;
explain and apply the cut property in a realistic implementation;
explain and apply Kruskal's algorithm in a realistic implementation;
explain and apply Prim's algorithm in a realistic implementation;
explain and apply ties and uniqueness in a realistic implementation.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before you start, retrieve one concrete example from a previous project in which you had to connect several things as cheaply or simply as possible. The example might involve network links, service dependencies, or a set of locations. It does not need to be an MST problem; it is there to make the constraint familiar.

The goal is not to memorize two algorithm names and reproduce a template. You should be able to make a defensible choice in an interview-sized problem and in a production data-processing problem. That means reasoning from the graph's size, density, connectivity, edge weights, and required output instead of assuming that the first familiar algorithm is always appropriate.

Terminology

Spanning tree: A spanning tree connects every vertex in a connected graph, uses exactly V-1 edges, and contains no cycle. If the graph is disconnected, the corresponding result is a spanning forest, with one tree per connected component.
Cut property: For a cut that separates the vertices into two sets, a lightest edge crossing that cut is safe to include in some minimum spanning tree. This is the principle that lets greedy algorithms make progress without losing optimality.
Kruskal: Kruskal sorts all edges by weight and considers them in that order, adding an edge only when its endpoints are currently in different components. A disjoint-set union structure makes that component check efficient.
Prim: Prim grows one tree from a starting vertex by repeatedly choosing the cheapest edge from the current tree to a vertex outside it. A priority queue is the usual implementation, especially when the graph is represented sparsely.
Ties and uniqueness: Equal-weight choices can lead to different edge sets with the same minimum total weight. A minimum spanning tree is therefore not necessarily unique, even though the minimum total weight is well-defined.
Use cases: An MST represents minimum-cost connectivity or backbone problems, some clustering variants, and geometric networks. It is not a shortest-path tree: the path between two vertices inside an MST need not be the globally shortest path between those vertices.

Mental model

Treat Minimum Spanning Trees: Kruskal, Prim, Cut Property, and Use Cases as a design problem with observable inputs, outputs, invariants, and failure modes. Given a weighted, undirected graph, an MST connects every vertex while minimizing the sum of the selected edge weights. That objective is different from shortest paths, which minimize the cost of traveling between particular vertices. Confusing those objectives is one of the most common mistakes in this topic.

A strong implementation makes its assumptions visible. It states whether the graph is expected to be connected, whether parallel edges and equal weights are allowed, how vertices are identified, and what the caller receives when no spanning tree exists. It also leaves enough evidence—tests, types, constraints, metrics, or diagrams—to show why the design is safe. The key invariants are straightforward: a selected set of edges must remain acyclic, each accepted edge must join different components, and a completed tree must contain V-1 edges and connect all V vertices.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. Then choose the mechanism that enforces it. For example, DSU is not just a convenient API in Kruskal; it is the mechanism that answers whether adding an edge would close a cycle. Likewise, Prim's priority queue is not the objective itself; it is a way to retrieve the cheapest boundary edge efficiently.

Deep dive

1. Spanning tree

Suppose several vertices need to remain connected, but every connection has a cost. Keeping every available edge is wasteful and may create cycles; selecting too few edges leaves part of the graph unreachable. A spanning tree is the minimal shape that connects all vertices: it has exactly V-1 edges and no cycle. In a connected graph, any one of those properties implies the other with the appropriate edge count.

A disconnected graph cannot have one spanning tree. It has a spanning forest instead, and an implementation should not silently report that forest as a complete solution if the requirement says every vertex must be connected. A useful completion check is that the chosen edge count is V-1 and all vertices belong to one component. For a forest, the number of chosen edges is V-C, where C is the number of connected components.

Decision rule: Use a spanning tree when the contract is about connecting all vertices with no redundant links, and make the connectivity requirement explicit. If the requirement is actually about shortest routes, resilience through redundant edges, or preserving multiple possible paths, a tree may be the wrong model even if it uses fewer edges.

2. Cut property

Imagine placing some vertices on one side of a boundary and the remaining vertices on the other. Any edge with one endpoint on each side crosses that cut. If an edge is the lightest edge crossing the cut, the cut property says that edge is safe: there is an MST containing it. If several crossing edges tie for lightest, each tied edge is safe in the appropriate sense, but choosing one may lead to a different valid MST than choosing another.

This property is the reason a greedy choice can be justified rather than merely guessed. Kruskal considers a cut between two current components; the cheapest edge joining them is safe. Prim considers the cut between the vertices already in its tree and the vertices outside it; the cheapest boundary edge is safe. The proof does not say that every cheap edge is safe. The edge must be the lightest crossing edge for a cut compatible with the choices already made.

Decision rule: Use the cut property as a proof tool when you need to justify a greedy edge choice or explain why an implementation cannot be improved by replacing that choice. If the graph is directed, the weights do not represent an undirected connectivity cost, or the requirement is shortest-path distance, do not apply the MST argument without first changing the model.

3. Kruskal

Kruskal sorts the graph's edges from lightest to heaviest and examines them in that order. It accepts an edge when its endpoints are in different components and skips it when both endpoints are already connected. The accepted edge joins two trees; the skipped edge would create a cycle. Continue until the graph has V-1 accepted edges or until all edges have been considered.

The disjoint-set union (DSU) structure represents the current components. find identifies an endpoint's representative, and union merges two different components. Path compression and union by rank or size make these operations nearly constant amortized time, commonly written as O(alpha(V)), where alpha is the inverse Ackermann function. The dominant cost is sorting: O(E log E), with O(V) additional DSU storage. The algorithm needs O(E) space to hold or sort the edge list, in addition to that DSU storage.

The invariant is that the accepted edges form a forest. Before accepting (u, v), compare find(u) and find(v). Equal representatives mean that a path already exists between the endpoints, so accepting the edge would create a cycle. Different representatives mean that the edge safely joins two components. If fewer than V-1 edges are accepted, the input graph was disconnected and no single MST exists.

Decision rule: Use Kruskal when the edge list is readily available, sorting is acceptable, and you want a direct component-based implementation. It is often a clear choice for sparse graphs or when the result naturally begins as an edge list. If repeatedly selecting boundary edges without sorting all edges is a better fit for the representation, compare it with Prim instead.

4. Prim

Prim starts with one vertex and grows a single tree. At each step, it chooses the cheapest edge whose one endpoint is already in the tree and whose other endpoint is outside it. A priority queue stores candidate boundary edges. After adding a vertex, its outgoing edges become candidates; entries that point to vertices already included are ignored when removed from the queue.

The invariant is that the selected vertices form one connected tree, and the next chosen edge is the lightest edge crossing the cut between that tree and the remaining vertices. With a binary heap and an adjacency-list representation, the typical running time is O(E log V), with O(V+E) graph and heap-related storage. With an adjacency matrix and a simple array selection, the common bound is O(V^2), which can be reasonable for dense graphs.

Prim's result depends on the starting vertex only when ties permit multiple valid MSTs; the total minimum weight remains the same for a connected undirected graph. As with Kruskal, an implementation must detect disconnected input. If the heap empties before every vertex has been included, the remaining vertices are in another component and the requested spanning tree does not exist.

Decision rule: Use Prim when the graph is naturally represented by adjacency lists or a matrix and you want to grow connectivity from a chosen starting point. It is a natural fit when maintaining the current tree and its boundary is simpler than sorting a global edge list. Do not choose it merely because a priority queue is available; representation, density, and the required output still determine the trade-off.

5. Ties and uniqueness

Equal-weight edges make the edge set a separate question from the total cost. Two algorithms, or two runs of the same algorithm with different tie ordering, may select different edges and still produce MSTs with exactly the same weight. A deterministic tie-breaker can make output reproducible, but it does not make the mathematical MST unique.

There is a useful distinction here. If every edge weight in a connected graph is distinct, the MST is unique. Repeated weights do not automatically imply multiple MSTs; they only make multiple choices possible. To claim uniqueness, reason about the graph and its cuts rather than assuming that the first result returned by an implementation is the only valid one.

Decision rule: Use explicit tie handling when downstream systems compare edge sets, cache results, generate snapshots, or need reproducible tests. If the contract only requires minimum total weight and connectivity, accept any valid MST and test those properties instead of over-constraining the exact edge order.

6. Use cases

An MST is appropriate when the requirement is to connect all locations or components at minimum total construction cost: for example, laying a network backbone, connecting sites with links, or building a low-cost geometric network. Removing any edge from a tree disconnects it, so the result is economical but has no built-in redundancy. If a link failure must not partition the network, an MST alone is insufficient.

MSTs also support some clustering approaches. Removing the most expensive edges from an MST can separate the graph into clusters, and geometric algorithms can use an MST to connect points with limited total length. These are models of global connectivity, not a general replacement for routing. The unique path between two vertices in the MST can be more expensive than the shortest path available in the original graph, because preserving the cheapest overall backbone is a different optimization problem.

Decision rule: Use use cases deliberately when the business requirement is minimum-cost global connectivity, a connectivity backbone, or a related clustering construction. Choose shortest-path algorithms for route distance, and choose a redundancy-aware design when availability or fault tolerance is part of the contract.

Worked example

Consider an interview-sized problem and a production data-processing problem. In both cases, begin by writing the requirement in one sentence, listing the input and output contracts, and identifying which concept owns each failure mode. For an MST, the input contract should say that the graph is weighted and undirected, and it should state whether disconnected input is an error or should produce a forest. The output contract should distinguish the selected edges from their total weight and should say whether edge ordering is significant.

The important move is separation. Parsing and validation belong at the boundary; graph and MST rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes malformed edges, duplicate records, missing vertices, and retry behavior much harder to reason about.

The small function below is intentionally not an MST implementation. It is a compact reminder to state the invariant before choosing a data structure. It also exposes a boundary decision: the empty input returns 0, while a missing value is not represented separately by this type.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

For the MST lab, make the equivalent invariant explicit: accepted edges form a forest in Kruskal, or the selected vertices form one connected tree in Prim. Walk the example with at least four cases: the normal connected graph, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. In graph terms, include a disconnected graph and a graph with tied edge weights; those cases reveal whether the implementation is confusing a forest with an MST or treating one valid edge set as uniquely required.

This is the level of explanation expected in a senior code review or technical interview: not just which algorithm returned a number, but which contract it satisfies, which invariant protected the result, and what evidence shows that failure was handled at the right boundary.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how graph data behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed records, schema changes, and high cardinality. An MST computed from a partial edge import may be internally valid while being wrong for the real network. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

For large inputs, sorting all edges can dominate Kruskal's runtime and memory, while an adjacency representation can dominate Prim's storage. Measure input size, density, and the frequency of recomputation before changing algorithms. If edge weights arrive from external or persisted data, validate their type and range at the boundary; do not assume a client-side check makes the server's graph safe.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations, especially if the graph is assembled from records that can change during computation. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. An MST's mathematical correctness does not validate authorization, data provenance, or operational freshness.

Guided lab

Implement Kruskal with DSU and Prim with a heap. Compare total weight and chosen edges on a graph with ties, then contrast the MST path to the Dijkstra shortest path. The comparison should show two separate facts: both MST algorithms can agree on minimum total weight while choosing different tied edges, and the path inside the MST can be longer than the shortest path in the original graph.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the tests, include a connected graph with a known total, a disconnected graph, duplicate or parallel edges, and tied weights. Verify the forest invariant while processing, the final edge count, connectivity, and the sum of selected weights. Do not assert one exact edge set unless the lab intentionally defines a deterministic tie-breaker. For the Dijkstra comparison, use the same original graph and explain why the two algorithms answer different questions.

Edge cases and failure modes

Spanning tree: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Also test a graph with zero or one vertex, a disconnected graph, and the distinction between a valid forest and a complete spanning tree.
Cut property: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include tied lightest crossing edges and verify that the proof is not being applied to a directed or shortest-path problem.
Kruskal: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check that cycle-forming edges are skipped, negative and equal weights are handled, and disconnected input is reported rather than mislabeled as an MST.
Prim: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check stale heap entries, already included vertices, disconnected input, and both sparse and dense representations where relevant.
Ties and uniqueness: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify minimum weight and connectivity rather than assuming that tied inputs have one canonical edge set.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. In particular, do not use Dijkstra when the requirement is global minimum-cost connectivity.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values. These choices can conceal a disconnected graph or a malformed edge until the result reaches production.
Testing only the happy path and therefore discovering contracts only after integration. A disconnected graph, an empty graph, parallel edges, and tied weights should be deliberate tests.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement. Kruskal's sort and Prim's representation have different costs depending on V, E, and density.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees. The client cannot be trusted to define which graph data may be used.

For debugging, reproduce the smallest failing case, inspect the actual edges, representatives, heap entries, and total weight, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. If Kruskal accepts a cycle, inspect DSU initialization and find/union behavior. If Prim selects an invalid edge, inspect visited-state handling and stale priority-queue entries. If the total is unexpectedly correct but the edge set differs, check for ties before treating the result as a bug.

Interview questions

What problem does Spanning tree solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Cut property solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Kruskal solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Prim solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Ties and uniqueness solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Minimum Spanning Trees: Kruskal, Prim, Cut Property, and Use Cases to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. Be prepared to explain whether your example is connected, how ties are handled, what the runtime and storage costs are, and why an MST rather than a shortest-path algorithm matches the requirement.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.