Ga naar inhoud

1. Prim's Algorithm

Prim's algorithm computes the minimum spanning tree (MST) of a connected, undirected, weighted graph by growing the tree one vertex at a time. Starting from an arbitrary root, it repeatedly selects the minimum-weight edge that connects a vertex already in the tree to a vertex outside the tree. The algorithm is structurally identical to Dijkstra's shortest-path algorithm — both maintain a priority queue of vertices prioritised by a key — but Prim keys on the minimum edge weight to the current tree rather than total path cost 12.

1.1 Problem Statement

(Same as Kruskal.) Given a connected, undirected, weighted graph \(G = (V, E, w)\), find a spanning tree \(T \subseteq E\) minimising \(\sum_{e \in T} w(e)\).

Variables
Symbol Meaning
\(G = (V, E, w)\) Weighted undirected graph
\(r\) Root of the MST (arbitrary starting vertex)
\(\text{key}[v]\) Minimum weight of an edge from \(v\) to the current tree
\(\pi[v]\) Parent of \(v\) in the MST
\(Q\) Min-priority queue keyed by \(\text{key}[\cdot]\); contains vertices not yet in the tree
$n = V

1.2 The Algorithm

PRIM(G, w, r):
  for each vertex u ∈ V:
    key[u] = ∞;  π[u] = NIL
  key[r] = 0
  Q = V (min-priority queue keyed by key)
  while Q ≠ ∅:
    u = EXTRACT-MIN(Q)          // add u to the MST
    for each v ∈ Adj[u]:
      if v ∈ Q and w(u, v) < key[v]:
        π[v] = u
        key[v] = w(u, v)
        DECREASE-KEY(Q, v, key[v])

The MST edges are \(\{(\pi[v], v) : v \neq r\}\).

1.2.1 Structural Analogy with Dijkstra

Feature Prim Dijkstra
Priority key key[v] = min edge weight to tree d[v] = total path cost from source
Invariant on settled set All tree edges so far form a partial MST All settled vertices have correct shortest distance
Update condition w(u, v) < key[v] d[u] + w(u,v) < d[v]

1.3 Correctness: Cut Property

Like Kruskal's, Prim's correctness rests on the cut property. At each step, let \(S\) be the set of vertices already in the tree. Prim picks the minimum-weight edge in the cut \((S, V \setminus S)\). By the cut property, this edge belongs to some MST. By induction, the entire tree is a minimum spanning tree on termination.

1.4 Complexity

Priority queue EXTRACT-MIN DECREASE-KEY Total
Array (linear scan) \(O(V)\) \(O(1)\) \(O(V^2)\)
Binary heap \(O(\log V)\) \(O(\log V)\) \(O((V+E) \log V)\)
Fibonacci heap \(O(\log V)\) amort. \(O(1)\) amort. \(O(E + V \log V)\)

For dense graphs (\(E \approx V^2\)) the \(O(V^2)\) array implementation is preferable. For sparse graphs (\(E = O(V)\)) the binary heap gives \(O(V \log V)\).

1.5 Comparison with Kruskal

Property Prim Kruskal
Approach Grows one connected component from a root Merges multiple components
Requires Connected graph Connected graph (forest generalises)
Data structure Priority queue Union-Find + sorted edges
Dense graphs \(O(V^2)\) \(O(V^2 \log V)\)
Sparse graphs \(O((V+E) \log V)\) \(O(E \log E) \approx O(E \log V)\)
Parallel Hard Easier (sort-then-scan)

1.6 Applications

  • Network design (same as Kruskal)
  • Approximate TSP: compute MST then do a pre-order DFS to get a Hamiltonian cycle that is at most \(2 \times\) optimal weight (Christofides / double-tree approximation)
  • Hierarchical clustering: MST-based single-linkage cluster hierarchy
  • Maze generation: random Prim = randomised MST produces uniform spanning tree mazes

1.7 Interactive Demo

The canvas shows Prim's algorithm growing the MST from vertex 0 on the same 10-vertex graph as the Kruskal demo. The current tree (blue vertices + green edges) grows one edge at a time; the priority queue frontier is shown with current key values.

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 4th edition, 2022. ISBN 978-0-262-04630-5. ↩

  2. Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 1st edition, 2006. ISBN 978-0-321-29535-4. ↩