Minimum Spanning Trees: Kruskal's and Prim's Algorithms Explained

In plain words — and an analogy

Imagine a utility company that needs to run electrical cable to five remote villages. Any two villages can be directly connected, but each link has a different cost. The company wants every village connected to the grid — but paying for redundant connections is waste. The cheapest solution is a minimum spanning tree: connect all five with exactly four cable runs (V−1 edges for V villages), no loops, lowest possible total cost. This is one of the most practical optimisation problems in computing, appearing in network design, clustering, image segmentation, and approximation algorithms.

Shortest paths asked: cheapest route from A to everywhere? The minimum spanning tree (MST) asks a different question: what's the cheapest way to connect *every* vertex into one piece, with no wasted links? The answer is always a tree: connected, V − 1 edges, no cycles (any extra edge would create a cycle and add cost for no new connectivity).

What makes it a tree

A spanning tree of a connected undirected graph is a subset of edges that touches all V vertices and forms a tree — so exactly V − 1 edges, connected, acyclic. A graph has many spanning trees; the minimum spanning tree is one of least total edge weight (there can be ties). MSTs are defined only for weighted, connected, undirected graphs; a disconnected graph has a *spanning forest* instead.

Graph:
  A ---1--- B
  |         |
  3         2
  |         |
  C ---4--- D

All spanning trees (V=4 → 3 edges each):
  Tree 1: A-B(1), B-D(2), A-C(3)  total = 6  ← MST
  Tree 2: A-B(1), B-D(2), C-D(4)  total = 7
  Tree 3: A-B(1), A-C(3), C-D(4)  total = 8
  Tree 4: B-D(2), A-C(3), C-D(4)  total = 9
  ... (and more)

Minimum total = 6  →  edges {A-B, B-D, A-C} form the MST.

Why greedy is provably correct here

Unlike most problems where greedy fails, MST greedy *works* — guaranteed — thanks to the cut property: for any way of splitting the vertices into two groups (a 'cut'), the cheapest edge crossing that cut is safe to include in some MST. Both algorithms are just two ways of repeatedly exploiting this: each step adds a minimum-weight edge that safely extends the tree, and the cut property certifies that no such choice can ever paint you into a corner. This is a rare and satisfying case where the obvious greedy instinct is also optimal — Lesson 24 on greedy algorithms uses MST as its headline example of when greedy is safe.

Kruskal's algorithm: cheapest edges first

Kruskal's builds the MST from the *edges* outward, globally: sort all edges by weight, then add them cheapest-first, skipping any edge that would form a cycle. The cycle test is the interesting part — it's exactly what union-find / disjoint-set (Lesson 28) is built for.

Kruskal(graph):
  mst_edges = []
  uf = UnionFind(graph.vertices)    // each vertex in its own set
  edges = sorted(graph.edges, key=lambda e: e.weight)

  for (u, v, w) in edges:
    if uf.find(u) != uf.find(v):   // different components?
      mst_edges.append((u, v, w))
      uf.union(u, v)
    if len(mst_edges) == V - 1:
      break                         // MST complete

  return mst_edges

Worked example: Kruskal traced step by step

Vertices: A, B, C, D, E
Edges sorted: A-B(1), B-C(2), A-C(3), C-D(4), A-D(5), D-E(6)

Step | Edge    | Same set? | Action           | Components
-----|---------|-----------|------------------|-----------------------------
  1  | A-B (1) |    No     | Add to MST       | {A,B} {C} {D} {E}
  2  | B-C (2) |    No     | Add to MST       | {A,B,C} {D} {E}
  3  | A-C (3) |   YES     | SKIP (cycle!)    | still {A,B,C} {D} {E}
  4  | C-D (4) |    No     | Add to MST       | {A,B,C,D} {E}
  5  | D-E (6) |    No     | Add to MST       | {A,B,C,D,E}  ← done!

MST edges: A-B, B-C, C-D, D-E   total weight = 1+2+4+6 = 13
(A-D(5) was never needed; A-C(3) was skipped as a cycle)

The dominant cost is sorting: O(E log E), which equals O(E log V) since E < V². The union-find operations are effectively O(1) each (near-constant amortized — Lesson 28 explains why). Kruskal's naturally suits sparse graphs and any situation where you already have a sorted edge list.

Prim's algorithm: grow one tree from a vertex

Prim's builds the MST from a *vertex* outward, locally: start with any single vertex and repeatedly attach the cheapest edge that connects the growing tree to a vertex not yet in it. It mirrors Dijkstra's structure almost exactly — a priority queue of frontier edges — differing only in what the queue is keyed on (edge weight to the tree, versus total distance from the source).

Prim(graph, start):
  in_tree = {start}
  mst_edges = []
  pq = MinHeap()
  for each edge (start→v, w): pq.push((w, start, v))

  while pq is not empty and len(in_tree) < V:
    w, u, v = pq.pop()
    if v in in_tree: continue        // v already in tree → skip
    in_tree.add(v)
    mst_edges.append((u, v, w))
    for each edge (v→x, wx):
      if x not in in_tree:
        pq.push((wx, v, x))

  return mst_edges

Kruskal vs Prim

Both produce a minimum spanning tree of the same total weight (the trees themselves can differ when weights tie), and both are greedy justified by the cut property. The choice is about the graph's shape and how it's given, not correctness — Kruskal leans sparse and edge-listed, Prim leans dense and adjacency-listed.

Under the hood: the cut property proof

A cut is any partition of V into two non-empty sets S and V−S. The cut property states: if e is the unique minimum-weight edge crossing a cut (S, V−S), then e belongs to every MST. Proof by contradiction: suppose e is not in some MST T. Adding e to T creates a cycle, and that cycle must contain at least one other edge e' crossing the cut. Replace e' with e: since w(e) < w(e'), the resulting tree has lower total weight — contradicting T being a minimum spanning tree. Both Kruskal's and Prim's repeatedly pick the minimum crossing edge for some cut, so by the cut property they never make a wrong choice.

Common pitfalls

• Confusing MST with shortest path. An MST minimizes *total* connection cost; it does *not* give shortest paths between specific vertices. The path between two nodes in an MST can be far longer than their true shortest path. Different problems, different algorithms.
• Kruskal without union-find. Detecting cycles by graph traversal on every edge is O(V·E) and defeats the algorithm. Union-find makes the cycle check near-constant — it's not optional.
• Applying MST to directed graphs. MST is an undirected notion. The directed analogue (minimum arborescence) needs a different algorithm entirely.
• Assuming the MST is unique. With tied edge weights, multiple distinct MSTs exist; algorithms may return any of them. All have the same total weight.
• Forgetting connectivity. MST algorithms assume the graph is connected. On a disconnected graph they produce a minimum spanning *forest* (one tree per component), not a single tree.

Practice problems

1. Min cost to connect all points. Given n points on a 2-D plane, find the minimum total cost to connect all points where the cost of connecting two points is their Manhattan distance. (Build a complete weighted graph and run Kruskal's or Prim's.)
2. Minimum cost to supply water. You have n houses; you can either build a well at a house or lay pipes between houses. What is the minimum total cost to supply water to all houses? (Add a virtual source vertex with well-cost edges, then find the MST of the expanded graph.)
3. Critical connections in a network. Find all edges whose removal disconnects the network. (These are edges that do NOT belong to any cycle — a different problem from MST, but the spanning tree concept is the starting point for Tarjan's bridge-finding algorithm.)

Key takeaways

• An MST connects all V vertices with V − 1 acyclic edges of minimum total weight.
• Greedy is provably optimal here via the cut property — the cheapest edge across any cut is always safe.
• Kruskal: sort edges, add cheapest-first, skip cycles via union-find — O(E log E), great for sparse graphs.
• Prim: grow one tree from a vertex, always attaching the cheapest frontier edge via a priority queue — O((V+E) log V), great for dense graphs.
• MST is not shortest paths; it's minimum total connectivity — keep the two problems distinct.

That closes the graph algorithms arc. The course now shifts from structures to the great algorithm families, starting with the most-studied task in computing: sorting — merge sort, quicksort, and heapsort. Practice MST tracing in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play