Minimum Spanning Trees: Kruskal and Prim: short notes (Algorithms)

Introduction

A spanning tree of a connected undirected graph $G=(V,E)$ is a subset of $E$ that connects all vertices and forms a tree ( $|V|-1$ edges, no cycle). A minimum spanning tree (MST) is a spanning tree of minimum total edge weight. Kruskal's and Prim's algorithms both grow an MST by the greedy cut property and are the GATE syllabus algorithms for this topic.

Prerequisites

Greedy Algorithms: greedy-choice property and safe edges.
Graph Representations: adjacency lists for Prim.
Union-Find (Disjoint Set) for Kruskal: makeset, find, union in nearly constant amortized time.

Core concepts

Cut property

A cut $(S, V\setminus S)$ partitions the vertices. An edge crosses the cut if its ends lie in different sides. A light edge for the cut is a crossing edge of minimum weight. If $A$ is a subset of some MST and the cut respects $A$ (no edge of $A$ crosses), then every light edge crossing the cut is safe to add to $A$ (CLRS 3e, Theorem 23.1).

Cycle property

If an edge $e$ is a maximum-weight edge on some cycle, then some MST avoids $e$ (CLRS Exercise 23.1-5). If $e$ is the unique heaviest edge on that cycle, then no MST contains $e$ : any spanning tree that uses $e$ can swap it for a lighter edge of the cycle that crosses the same cut. Kruskal's rejections are exactly this rule in action: a rejected edge closes a cycle whose other edges were all accepted earlier and are no heavier.

Cut versus cycle. The cut property certifies an edge in an MST (lightest across some cut); the cycle property certifies an edge out of it (heaviest on some cycle). Every edge of an MST is a light edge for some cut (CLRS Exercise 23.1-3).

Algorithms and pseudocode

Pseudocode uses <- for assignment. Kruskal uses a disjoint-set structure; Prim uses a min-priority queue keyed by key.

Kruskal

Text

MST-KRUSKAL(G, w)
1  A <- empty set
2  for each vertex v in G.V
3      MAKE-SET(v)
4  sort the edges of G.E into nondecreasing order by weight w
5  for each edge (u, v) in that order
6      if FIND-SET(u) != FIND-SET(v) then
7          A <- A union {(u, v)}
8          UNION(u, v)
9  return A

Time. Sorting $O(E \lg E)$ ; the Union-Find loop is $O(E\,\alpha(V))$ . Overall $O(E \lg E)$ (or $O(E \lg V)$ since $E < V^2$ ).

Prim

Text

MST-PRIM(G, w, r)
1  for each u in G.V
2      u.key <- infinity
3      u.pi <- NIL
4  r.key <- 0
5  Q <- G.V                                    // min-priority queue on key
6  while Q is not empty
7      u <- EXTRACT-MIN(Q)
8      for each v in Adj[u]
9          if v in Q and w(u, v) < v.key then
10             v.pi <- u
11             v.key <- w(u, v)               // DECREASE-KEY
12 return {(v.pi, v) : v in G.V - {r}}

Time. Binary heap: $O(E \lg V)$ . Fibonacci heap: $O(E + V \lg V)$ . Adjacency-matrix Prim: $O(V^2)$ .

Algorithm and data structure	Time	Best for
Kruskal, comparison sort plus union-find	$O(E \lg E) = O(E \lg V)$	sparse graphs, edges given as a list
Prim, array of keys (scan for the minimum)	$\Theta(V^2)$	dense graphs, $E = \Theta(V^2)$
Prim, binary heap	$O((V+E) \lg V)$ , that is $O(E \lg V)$ for connected graphs	sparse graphs
Prim, Fibonacci heap	$O(E + V \lg V)$	theory; dense and sparse

On a dense graph, array-based Prim's $\Theta(V^2)$ beats the binary-heap version's $\Theta(V^2 \lg V)$ .

Edge cases. Disconnected graphs have spanning forests; both algorithms extend naturally (Kruskal already produces a forest; Prim needs a loop over unused roots). Equal weights: MSTs need not be unique; both algorithms are correct for any tie-break. Negative weights are allowed (unlike Dijkstra).

Union-Find cost in Kruskal

With path compression and union by rank the disjoint-set operations run in amortized $O(\alpha(V))$ time, where $\alpha$ is the inverse Ackermann function (at most 4 for all practical $V$ ). The bottleneck is therefore the initial sort of the edges. If weights are integers in a small range, counting sort or radix sort can replace the comparison sort and the Union-Find term may dominate, giving nearly linear time in $E$ .

Prim versus Dijkstra

Both algorithms maintain a priority queue of unsettled vertices and repeatedly extract the minimum key. The difference is the key:

	Prim	Dijkstra
Key of $v$	weight of the lightest edge from the tree to $v$	tentative distance $\delta(s,v)$
Relaxation	`key[v] <- min(key[v], w(u,v))`	`d[v] <- min(d[v], d[u]+w(u,v))`
Requires	undirected graph	directed or undirected; nonnegative weights

Replacing Prim's key update by Dijkstra's yields a shortest-path tree, not an MST. Triangle $s, a, b$ with $w(s,a) = w(s,b) = 2$ and $w(a,b) = 1$ : every MST contains $ab$ and one of the two edges at $s$ , total 3. The shortest-path tree from $s$ uses $sa$ and $sb$ (distances 2 and 2), total 4, so it is not an MST.

Transforming the weights

Every spanning tree has exactly $|V| - 1$ edges, and Kruskal looks only at the order of the weights. Hence:

Adding a constant $c$ to every weight keeps every MST an MST; each tree's weight grows by $(|V|-1)c$ . Shortest paths behave differently: paths with more edges gain more, so shortest paths can change (Single-Source Shortest Paths).
Multiplying by a positive constant, or applying any strictly increasing function (squaring positive weights, for example), keeps the same MSTs.
Negative weights need no special handling.
Maximum spanning tree: negate all weights (or sort in decreasing order) and run either algorithm.
Bottleneck. An MST also minimises the largest edge weight among all spanning trees.
Singleton cuts. For each vertex, a lightest incident edge belongs to some MST; if it is the unique lightest, it belongs to every MST.

Mathematical explanation

Correctness via the cut property

Kruskal's accepted edge is light for the cut separating the two components it joins, so it is safe. Prim's extracted vertex $u$ is joined by a light edge across the cut $(V\setminus Q,\, Q)$ , so that edge is safe. Induction shows the final set is an MST.

Uniqueness

If every cut has a unique light edge, the MST is unique. The converse is false: a graph can have a unique MST while some cut has several light edges of equal weight (CLRS Exercise 23.1-6). Path $a{-}b{-}c$ with both edges of weight 1 is its own unique spanning tree, yet the cut $(\{b\}, \{a, c\})$ has two light edges.

Distinct weights give a unique MST (CLRS Problem 23-1), because then every cut has a unique light edge. With ties, several MSTs can exist: $K_4$ with all six weights equal has $4^{4-2} = 16$ spanning trees, and every one is an MST. All MSTs of a graph share the same sorted list of edge weights (CLRS Exercise 23.1-8).

Second-best MST

A second-best MST is a spanning tree of least weight among those that are not the (unique) MST. It differs from the MST by a single swap: add one non-tree edge $(u,v)$ and delete the heaviest MST edge on the tree path from $u$ to $v$ . Its weight is the minimum over non-tree edges of $w(MST) + w(u,v) - \max(\text{path edge})$ , and it need not be unique (CLRS Problem 23-1).

Worked examples

One graph, both algorithms

Vertices $a,b,c,d$ . Edges with weights: $ab:1$ , $ac:4$ , $ad:3$ , $bc:2$ , $bd:5$ , $cd:6$ .

Kruskal (sorted): $ab, bc, ad, ac, bd, cd$ .

Take $ab$ (components $\{a,b\},\{c\},\{d\}$ ).
Take $bc$ (components $\{a,b,c\},\{d\}$ ).
Take $ad$ (connects $d$ ). Stop. Reject $ac,bd,cd$ as cycles.

MST edges $\{ab,bc,ad\}$ , weight $1+2+3=6$ .

Prim from $a$ , keys of the vertices still in the queue after each EXTRACT-MIN (a blank cell means the vertex has already been extracted):

Extracted	key $b$	key $c$	key $d$	Edge added
$a$	1	4	3	none (root)
$b$		2	3	$ab$ (1)
$c$			3	$bc$ (2)
$d$				$ad$ (3)

Extracting $b$ lowers $c$ 's key from 4 to 2 (edge $bc$ ) but leaves $d$ at 3, since $bd = 5 > 3$ . Same tree as Kruskal.

Second-best tree for this graph. Try each non-tree edge: $ac$ (4) closes $a, b, c$ , whose heaviest tree edge is $bc$ (2), giving $6 + 4 - 2 = 8$ ; $bd$ (5) closes $b, a, d$ , dropping $ad$ (3), giving 8; $cd$ (6) closes $c, b, a, d$ , dropping $ad$ , giving 9. The second-best weight is 8, reached by two different trees, $\{ab, ac, ad\}$ and $\{ab, bc, bd\}$ . The graph has 16 spanning trees in all, and the MST of weight 6 is unique because the weights are distinct.

Cut property: light edge across a cut — Figure 1. Cut $(\{a,b\},\{c,d\})$ on the example graph: the light crossing edge is $bc$ of weight 2 (or $ad$ of weight 3 for a different cut); the cut property says a light crossing edge is safe for the MST.

Kruskal and Prim growing the same MST — Figure 2. Kruskal accepts $ab$ , $bc$ , $ad$ in that order; Prim from $a$ grows the same three edges; total weight 6.

Implementation checklist for MST questions

Before coding Kruskal, confirm the graph is undirected and that the Union-Find structure initialises one set per vertex. Sort edges stably only if the problem asks for a particular MST among ties; any total order by weight is correct for the weight optimum. Before coding Prim, initialise every key to infinity except the root, and treat the priority queue as containing all vertices (decrease-key) rather than inserting neighbours lazily, unless the lazy version is analysed carefully for duplicate entries.

For hand traces, draw/save the cut immediately before accepting each edge: for Kruskal use a pre-union component versus the rest; for Prim use the previously grown tree versus the rest. The accepted edge must be light across that cut. This picture is the fastest way to catch an off-by-one in a weight table during an exam.

Important properties and observations

MST weight is unique even when several MSTs exist; the sorted list of MST edge weights is the same for every MST (CLRS Exercise 23.1-8).
Prim resembles Dijkstra but keys are edge weights to the tree, not path weights from the root.
Kruskal needs sorting globally; Prim needs a dynamic priority queue.
Updating an MST after decreasing a tree edge keeps the same tree; after decreasing a non-tree edge, add it and delete the heaviest edge on the created cycle.

Common misconceptions.

"Prim requires nonnegative weights." False; Prim and Kruskal allow negatives.
"Dijkstra's tree is an MST." False in general: shortest-path trees minimise path weights from $s$ , not total edge weight.
"The MST is unique." Only under stricter conditions (for example distinct weights, or a unique light edge for every cut).
"Adding a constant to all weights can change the MST." It cannot, because every spanning tree has $|V| - 1$ edges. It can change shortest paths.

GATE examination perspective

TRACE KRUSKAL. Sort edges; skip those that unite the same component.
TRACE PRIM. Show key and $\pi$ after each extract-min.
CUT ARGUMENT. Name a cut and its light edge to justify an MST edge.
COMPLEXITY. Kruskal $O(E \lg E)$ ; Prim binary-heap $O(E \lg V)$ ; matrix Prim $O(V^2)$ .
MST VERSUS SHORTEST PATHS. Different objectives; the triangle with weights 2, 2, 1 separates them.
DISTINCT WEIGHTS. Unique MST. With ties, count trees carefully; the MST weight is still unique.
WEIGHT TRANSFORMS. Adding a constant or applying an increasing function preserves the MST.
SECOND-BEST. One edge swap from the MST; compute $w(MST) + w(e) - \max$ on the cycle for each non-tree edge $e$ .
DATA STRUCTURE. Dense graph: array Prim $\Theta(V^2)$ . Sparse graph: Kruskal or heap Prim $O(E \lg V)$ .

Summary

Greedy Algorithms: prerequisite. Safe local choices.
Graph Representations: prerequisite. Input for Prim.
Graph Connectivity: related. Cuts, bridges and connectivity.
Single-Source Shortest Paths: related. Dijkstra's similar loop with a different key.

Minimum Spanning Trees: Kruskal and Prim

Introduction

Prerequisites

Core concepts

Cut property

Cycle property

Algorithms and pseudocode

Kruskal

Prim

Union-Find cost in Kruskal

Prim versus Dijkstra

Transforming the weights

Mathematical explanation

Correctness via the cut property

Uniqueness

Second-best MST

Worked examples

One graph, both algorithms

Implementation checklist for MST questions

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Cut property

Cycle property

Algorithms and pseudocode

Kruskal

Prim

Union-Find cost in Kruskal

Prim versus Dijkstra

Transforming the weights

Mathematical explanation

Correctness via the cut property

Uniqueness

Second-best MST

Worked examples

One graph, both algorithms

Implementation checklist for MST questions

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps