Minimum Spanning Tree

Mental model

Both algorithms are the same greedy argument from different ends: the cut property says the lightest edge crossing any cut is safe, so Kruskal takes globally cheapest edges and uses union-find to reject cycles, while Prim grows one component and takes the cheapest edge leaving it. An MST minimises TOTAL weight, which is not the same as minimising any individual path — the MST route between two nodes can be far worse than their shortest path.

How to study Minimum Spanning Tree

Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use the linked roadmap and primary implementation references to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.

Next, compare Minimum Spanning Tree with Shortest Path, Greedy. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Total weight of a minimum spanning tree and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.

Proof of understanding

• Explain the mechanism from first principles and identify the state it reads or changes.
• Give one situation where the concept is the right choice and one where it is not.
• Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
• Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.

Where it matters

Network and cable layout, clustering by single linkage, and approximation algorithms for touring problems.

Common mistakes

• Expecting MST paths to be shortest paths — different objective entirely
• Running Kruskal without union-find, so cycle checks dominate the runtime
• Assuming the MST is unique; it is only unique when all edge weights differ
• Applying it to a directed graph, where the problem becomes arborescence and needs a different algorithm

Learn from primary sources

Use the linked roadmap context and practice prompt.

Practice and explain it back

Review prompts

• Someone proposes routing traffic along the MST because it is the cheapest set of edges. What is wrong with that reasoning?

Build evidence

Use a roadmap capstone to turn this concept into working evidence.

Learning paths

• DSA Practice