Graphs

Minimum Spanning Tree

Connect all nodes at minimum total cost with Kruskal's or Prim's algorithm.

Hard, optional depth, about 90 minutes to practise.

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

pop 1:1-2
1:1-2[0] root
2:2-3[1]
4:1-3[2]

Sort edges by weight. Union-find: each node is its own set.

edges.sort(key=lambda e: e.w)

Live template

Line 1 active

1edges.sort()
2for w, u, v in edges:
3 if union(u, v): total += w; used += 1
4return total if used == n - 1 else -1

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).

  1. Sort: 1, 2, 3, 4, 5.
  2. Add 1-2 (cost 1). Add 2-3 (cost 2). Skip nothing yet.
  3. Add 3-4 (cost 3). Now all connected; total 6. 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.

All lessons