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

The Minimum Spanning Tree Problem

Given a connected, undirected graph with weighted edges, a Spanning Tree is a subset of edges that connects all vertices without forming any cycle. A Minimum Spanning Tree (MST) is a spanning tree whose total edge weight is as small as possible. This problem models scenarios like connecting cities with the least total cable length, or wiring a circuit board using the minimum amount of connecting material.

Example graph with weighted edges:
A-B: 4    A-C: 8
B-C: 8    B-D: 11
C-D: 7    C-E: 2
D-E: 6    D-F: 4
E-F: 14

The minimum spanning tree connects all vertices
using the smallest possible total edge weight,
selecting exactly (V-1) edges with no cycles

The Generic MST Algorithm and the Cut Property

Both algorithms covered in this article are specific instances of a more general theorem that justifies a greedy approach to this problem. Define a Cut of a graph as a partition of its vertices into two disjoint sets, and an edge Crosses the cut if it connects a vertex in one set to a vertex in the other.

Cut Property (informal statement):
For any cut of the graph, if an edge crossing the cut
has strictly smaller weight than every other edge
crossing that same cut, that edge must be included
in every minimum spanning tree

This theorem, provable using an exchange argument similar in style to the ones used for the greedy algorithms discussed earlier in this series, is the foundation both Kruskal's and Prim's algorithms build upon: both algorithms repeatedly identify a "safe edge" — one guaranteed by the cut property to belong to some minimum spanning tree — and add it to the growing solution.

Kruskal's Algorithm: Sorting Edges Globally

Kruskal's Algorithm considers all edges in increasing order of weight, adding each edge to the growing forest unless doing so would create a cycle.

MST-KRUSKAL(G, w):
  A = empty set
  for each vertex v in G.V:
      MAKE-SET(v)
  sort the edges of G.E by weight, into non-decreasing order
  for each edge (u, v), in sorted order:
      if FIND-SET(u) ≠ FIND-SET(v):
          A = A ∪ {(u, v)}
          UNION(u, v)
  return A

This algorithm relies directly on the disjoint-set forest structure discussed earlier in this series to efficiently check whether adding an edge would create a cycle: two vertices are already connected if and only if they belong to the same disjoint set, meaning adding an edge between them would close a cycle rather than extend the tree.

Tracing Kruskal's Algorithm

Sorted edges: C-E(2), A-B(4), D-F(4), D-E(6), C-D(7),
              A-C(8), B-C(8), B-D(11), E-F(14)

Process C-E(2): different sets → add. MST: {C-E}
Process A-B(4): different sets → add. MST: {C-E, A-B}
Process D-F(4): different sets → add. MST: {C-E, A-B, D-F}
Process D-E(6): different sets → add. MST: {C-E, A-B, D-F, D-E}
Process C-D(7): same set (C-E-D-F connected) → skip, would create cycle
Process A-C(8): different sets → add. MST: {C-E, A-B, D-F, D-E, A-C}
(5 edges now connect all 6 vertices — MST complete)

Since sorting the edges takes O(E log E) time, and processing each edge with the near-constant-time disjoint-set operations discussed earlier in this series takes O(E α(V)) total time, the overall running time is dominated by the sort: O(E log E), which is equivalent to O(E log V) since E is at most V².

Prim's Algorithm: Growing a Single Tree

Prim's Algorithm takes a different approach: rather than considering edges globally, it grows a single tree starting from an arbitrary vertex, always adding the cheapest edge that connects the current tree to a new vertex not yet included.

MST-PRIM(G, w, r):
  for each vertex u in G.V:
      u.key = infinity
      u.p = NIL
  r.key = 0
  Q = priority queue containing all vertices in G.V, keyed by .key
  while Q is not empty:
      u = EXTRACT-MIN(Q)
      for each v in Adj[u]:
          if v is in Q and w(u, v) < v.key:
              v.p = u
              v.key = w(u, v)      // DECREASE-KEY operation
  // the edges (v, v.p) for all v ≠ r form the MST

This algorithm relies directly on the priority queue structure discussed earlier in this series regarding heaps: at every step, it efficiently extracts the vertex closest to the growing tree, and updates neighboring vertices' keys as new, cheaper connecting edges are discovered.

Tracing Prim's Algorithm

Starting from vertex A:
Extract A (key 0). Update: B.key=4, C.key=8
Extract B (key 4). Update: (no improvements, C.key stays 8)
Extract C (key 8, via A). Update: D.key=7, E.key=2
Extract E (key 2, via C). Update: D.key=6 (improved), F.key=14
Extract D (key 6, via E). Update: F.key=4 (improved, via D)
Extract F (key 4, via D)

Resulting MST edges: A-B, A-C, C-E, D-E, D-F

Using a binary heap for the priority queue, each of the V EXTRACT-MIN calls costs O(log V), and across all iterations, at most E DECREASE-KEY operations occur, each also costing O(log V), giving a total running time of O(E log V) — matching Kruskal's algorithm's asymptotic complexity, though the two algorithms arrive there through very different mechanisms.

Choosing Between Kruskal's and Prim's Algorithms

Kruskal's Algorithm:
  - Naturally suited to sparse graphs, since it processes
    edges globally and doesn't need to track a single
    growing frontier
  - Simple to implement given a disjoint-set structure
  - Easily parallelized across the sorted edge list

Prim's Algorithm:
  - Naturally suited to dense graphs, since it grows
    incrementally from a single source without needing
    to sort all edges upfront
  - Similar in structure to Dijkstra's shortest-path
    algorithm, covered later in this series
  - Using a Fibonacci heap for the priority queue can
    reduce the running time to O(E + V log V), an
    improvement over Kruskal's for very dense graphs

Why Minimum Spanning Trees Matter Beyond Network Design

Beyond the obvious network-design applications like telecommunications and utility infrastructure, minimum spanning tree algorithms appear as subroutines in image segmentation, approximation algorithms for harder problems like the traveling salesman problem, and clustering algorithms in machine learning, where the edges of a minimum spanning tree naturally reveal groupings of closely related data points. The cut property proven at the start of this article is a recurring proof technique throughout greedy graph algorithms, illustrating how a single elegant structural theorem can justify multiple different algorithmic approaches to the same underlying problem.