Unit 3.7 · about 4 h
110 / 324Minimum spanning trees with Kruskal and Prim
Minimum connection cost is the canonical greedy-with-proof: one theorem justifies two algorithms, and the input shape picks between them.
- derive
- implement
You can now
- Implement Kruskal with sorted edges plus union-find and lazy Prim with a frontier heap, stating each stale-entry rule.
- Prove accepted edges are safe with the cut-property exchange argument, and rejected edges with the cycle property.
- Choose Kruskal for explicit edge lists and Prim (dense \(O(V^2)\) or heap) for dense or implicit graphs.
Covers
- Minimum spanning trees with Kruskal and Prim
Study, in this order
3 steps
- Minimum spanning tree: Kruskal's algorithmDSA Handbook - graphs
The pattern (LC 1584); Why it works: the cut property; Worked example on the canonical 7-vertex graph (weight 31); Variants: virtual source node
Depth · Skim LC 1489's Kruskal-twice-per-edge on first pass; edge classification is stretch.
- Minimum spanning trees: Prim's algorithmDSA Handbook - graphs
The pattern with the
in_mstskip; When the graph is implicit: LC 1584; Dense Prim from \(O(n^2 \log n)\) to \(O(n^2)\); Kruskal vs Prim: the decision table - Minimum Spanning Trees, Chapter 7Algorithms - graph chapters
7.1 Distinct Edge Weights; 7.2 The Only Minimum Spanning Tree Algorithm (safe and useless edges); 7.3 Boruvka's Algorithm; 7.4 Jarnik's ("Prim's") Algorithm; 7.5 Kruskal's Algorithm (printed pp. 257-268)
Focus on
- Kruskal's guard is
union: accept iff endpoints sit in different components, stop at \(n - 1\) edges. The sort dominates at \(O(E \log E)\); the DSU loop is effectively linear. - Lazy Prim pushes
(weight, vertex)pairs and skips withif in_mst[u]: continue. The heap holds duplicates; the eager decrease-key variant needs an indexed heap no standard library ships. - Prim cumulates nothing: pushing distance-from-start plus edge weight builds a shortest-path tree, not an MST. Dijkstra cumulates, Prim does not.
- Every MST has the same total weight, and distinct weights also make the edge set unique. With ties, as in LC 1584, Kruskal and Prim may pick different edges but must report the same total.
Reproduce closed-book
[[0,0],[2,2],[3,10],[5,2],[7,0]]; both return 20. State the input size (\(n = 5\), complete graph of 10 Manhattan edges) and which variant each function is.Traps
- Early break on disconnected input: stopping is valid only when \(n - 1\) accepts happen. Otherwise walk every edge and
return -1when accepts fall short. - Integer totals in Java and C++: LC 1584 edge weights reach \(4 \times 10^{6}\) and 999 of them sum past
INT_MAX. Accumulate inlongorlong long; Python integers are exempt. - Forgetting either DSU heuristic: one-sided chains push finds to \(O(n)\) before compression ever fires. Ship path halving with union by rank as in the handbook reference.
Practice
LeetCode 1584: Min Cost to Connect All Points
The five-point example (answer 20) and the two-point example
Implement both Kruskal and Prim in one file and assert equal totals. Manhattan weights tie, so the chosen edges may differ, but a different total means a bug. After-attempt reference is DSA Handbook 8.11 and 8.12.
Self-test
-
Prove the cut property by exchange.
Let \(e\) be the lightest edge across cut \((S, V - S)\) and \(T^{*}\) an MST missing \(e\). Adding \(e\) creates a cycle with another crossing edge \(e'\) of weight at least \(w(e)\). Swapping \(e'\) for \(e\) keeps a spanning tree of no greater weight, so some MST contains \(e\). -
Why is a rejected Kruskal edge safe to drop?
Its endpoints already connect through accepted edges, each processed earlier hence no heavier. The closed cycle's other edges are all at most as heavy, so the rejected edge is a heaviest edge of that cycle and no MST needs it. -
Why does dense Prim beat heap Prim on LC 1584?
The complete graph materializes about 500,000 edges at \(n = 1000\); heap Prim pays \(O(n^2 \log n)\) on them while dense Prim scansmin_edgearrays for \(O(n^2)\) with no heap and no stale entries. -
Kruskal and Prim report different totals on the same input. What follows?
A bug: all minimum spanning trees share one total weight, so two correct runs agree on it even when tied weights let them choose different edges. Check the stale skip, the union guard and the weight function.
Completion criterion
Stop when
Your blank-file script prints 20 from both functions on the five-point input, and you can state the Kruskal-versus-Prim choice for an edge list, a dense matrix and a point set without hedging.
Mark passed, then open 3.8 Only mark this when you can do it without notes.Leads to
- 4.3 Greedy choice, optimal substructure and exchange arguments The cut property is the exchange argument in its cleanest form; carry it into greedy correctness proofs.
- 3.8 Graph certificates and exhaustive small-graph validation Verify your MST against brute force on \(n \le 8\) before trusting the greedy.
Comes after
- 3.5 Union-find with path compression and union by rankUnion-find becomes Kruskal's cycle check: sort edges, accept across components.
- 3.6 Dijkstra, Bellman-Ford and negative cyclesPrim reuses the frontier heap with one substitution: edge weight to the tree instead of path distance from the source.
- 4.4 Greedy counterexamples and interval schedulingThe cut argument is the next exchange proof.
Resources for this unit
- DSA Handbook - graphs Study all of Part 8 in order. For each algorithm, write the representation, invariant, forbidden input assumptions and independently checkable output before reading the implementation.
- Algorithms - graph chapters Use the basic graph, depth-first search, minimum spanning tree, shortest path and flow chapters, and lecture note 11 Disjoint Sets for union-find, for correctness proofs and counterexamples to tempting wrong algorithms.
Also in this section
- AlgoMaster DSA - graph slice Attempt Number of Islands, Course Schedule II and Network Delay Time cold. They cover traversal, dependency modeling and weighted shortest paths; add one narrative problem only if graph modeling remains weak.
- Hypothesis - generated graph tests Generate small sparse, dense, disconnected, cyclic, parallel-edge and weighted graphs. Compare optimized results with exhaustive or deliberately simple references and retain shrunk failures.
- NeetCode - unseen graph problems Use two unseen story problems without graph tags. Grade the model, assumptions, certificate and tests as well as the final answer.