1Understand
The idea
To connect every node at the lowest total cost, Kruskal's algorithm sorts edges by cost and adds each one unless it would close a cycle, which union-find detects. The cheapest edge across any split of the nodes is always safe to take, which is why this greedy choice is optimal.
Intuition
To connect every node at lowest total cost, Kruskal sorts edges by weight and adds each unless it would close a cycle, union-find detects that. Prim grows a tree from a start node by always taking the cheapest edge out.
The cut property says the cheapest edge across any partition of the vertices is safe, that is why the greedy choice is optimal.
MST needs an undirected weighted connected graph; directed "MST" is a different problem.
What you will be able to do
- Apply Kruskal with union-find
- Detect a disconnected graph
When to use it
- Connect all points / cities at minimum cost
- Cheapest network with no cycles
2See it
Walkthrough
Kruskal by lightest edge
Edges (1-2:1), (2-3:2), (1-3:4), add smallest unless it closes a cycle.
1 / 5
Sort edges by weight. Union-find: each node is its own set.
Live template
Line 1 active
Complexity: time O(E log E), space O(V)
Kruskal O(E log E) from sorting, plus nearly O(E) union-find. Prim with a heap is O(E log V). Prefer Kruskal on sparse edge lists; Prim when you already have adjacency lists and denser local growth.
Read the walkthrough as text
Kruskal on 4 nodes. Edges (1-2:1), (1-3:4), (2-3:2), (2-4:5), (3-4:3).
- Sort:
1,2,3,4,5. - Add
1-2(cost 1). Add2-3(cost 2). Skip nothing yet. - Add
3-4(cost 3). Now all connected; total6. Skip the rest (they cycle).
Prim would start at 1, repeatedly pick the lightest edge leaving the growing set, and get the same total.
3Recognise it
Kinds of problems (4)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Kruskal's algorithm
Example. Minimum total weight to connect all nodes.
How. Sort edges by weight; union if endpoints in different sets; stop at n−1 edges.
Prim's algorithm
Example. Grow MST from a start node.
How. Min-heap of frontier edges; add cheapest that reaches a new vertex.
Connect points on a plane
Example. MST over Euclidean distances between points.
How. Kruskal or Prim on all pairs (or spatial optimisation), same MST template.
Critical and pseudo-critical edges
Example. Edges that must appear in every MST.
How. Compare MST weight with edge forced in or banned, weight change flags critical.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Cycle edges taken
Why it happens. Adding edges in sorted order already minimises weight.
How it fails. Kruskal adds edge inside same component, cycle formed, not a tree.
Fix. Union must return true (different roots) before adding edge weight.
Confused with shortest path
Why it happens. Both problems minimise sums on graphs.
How it fails. Returns shortest path total instead of spanning all vertices with n−1 edges.
Fix. MST connects all nodes, minimises sum of tree edges, not s-t distance.
Disconnected graph
Why it happens. Partial edge set still has a “total weight”.
How it fails. Two components, used < n−1 edges, return cost anyway instead of failure.
Fix. Valid MST iff used == n, 1 after processing (for connected input).
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.