Graph AlgosAlgorithmaka Prim-Jarník, MST by growing a tree

Prim's Algorithm

Minimum spanning tree by growing one tree from a start node, always adding the cheapest edge that crosses from the tree to a new node.

▶ VisualizePattern: Heap / Priority QueuePractice (1)
Progress

Overview

A minimum spanning tree of a connected, undirected, weighted graph is a set of V - 1 edges connecting all nodes with minimum total weight. Prim's algorithm builds it the way Dijkstra's Algorithm builds shortest paths: keep a set of tree nodes, and repeatedly add the cheapest edge with exactly one endpoint in the tree. The difference is the key: Dijkstra keys a node by dist[u] + w (path length), Prim keys it by w alone (edge weight).

Complexity depends on the representation. With a Binary Heap over an Adjacency List: O(E log V). With an Adjacency Matrix and a linear scan for the minimum: O(V²). On dense graphs (E ≈ V²) the matrix version wins — O(V²) versus O(V² log V) — and it is the reason to prefer Prim over Kruskal's Algorithm there; on sparse graphs the two are comparable and Kruskal is often simpler.

minimum spanning treeMSTgreedypriority queuedense graphscut property

Intuition

A mental model before the formal terms.

Wiring houses to a power grid one at a time: start at the plant, and each step connect the unwired house that is cheapest to reach from any already-wired house. You never revisit a decision, and you never leave a gap, because the growing network stays a single connected tree until every house is on it.

How it works

  1. Pick any start node s; set key[s] = 0, all other key = ∞; nothing is in the tree yet.
  2. Heap version: push (0, s). Pop the smallest (k, u); if u is already in the tree, skip. Otherwise add u to the tree (and the edge parent[u] – u to the MST if u ≠ s).
  3. For each edge u – v with weight w where v is not in the tree: if w < key[v], set key[v] = w, parent[v] = u, push (w, v).
  4. Repeat until the heap is empty. The graph is connected iff V nodes ended up in the tree.
  5. Matrix version for dense graphs: V rounds, each scanning all V keys for the minimum non-tree node, then scanning its matrix row to update keys — O(V²) with no heap.

Why it works

Cut property: for any partition of the nodes into S and V \ S, the minimum-weight edge crossing the cut belongs to some MST. Proof: take an MST T not containing that edge e; adding e to T creates a cycle that must cross the cut on another edge e' with w(e') ≥ w(e); swapping e' for e gives a spanning tree no heavier than T.

Prim applies the cut property with S = the current tree at every step: the popped edge is the lightest one crossing the cut, so adding it keeps the tree a subset of some MST. After V - 1 additions it is an MST.

Complexity: each edge is pushed at most twice (once per endpoint) → O(E) heap operations of O(log E) = O(log V) each.

Recognition

How to tell a problem wants this.

  • "Minimum cost to connect all points/cities/computers", "minimum total cable length".
  • The graph is dense or implicitly complete (every pair of points has an edge, e.g. Euclidean distances) — Prim with O(V²) avoids materialising and sorting V² edges.
  • Edges are discovered on the fly from a node (grid neighbourhoods), which suits a node-centric algorithm.
“k most frequent” → Heap / Priority Queue“maximum number of non-overlapping” → Greedy

Interactive visualization

Play, step, change the input. ← → and space work too.

42518103263A0B∞C∞D∞E∞F∞G∞
key / parent
nodekeyparent
A0—
B∞—
C∞—
D∞—
E∞—
F∞—
G∞—
1/19Start Prim at A with key 0; every other key is ∞. key[v] is the cheapest known edge connecting v to the growing tree.
Node just addedCandidate (has finite key)In treeBest edge into a candidateMST edge
PseudocodeLearn Prim's Algorithm →
1key = {v: ∞}; key[start] = 0; inTree = {}
2while some node is not in tree:
3  u = node not in tree with minimum key
4  inTree.add(u); add edge (parent[u], u) to MST
5  for (v, w) in neighbors(u):
6    if v not in tree and w < key[v]:
7      key[v] = w; parent[v] = u
Variables
startA
Complexity
best O(E log V)
avg O(E log V)
worst O(E log V)
space O(V + E)
Speed

Pseudocode

1key = [INF] * n; key[s] = 0; inTree = [false] * n; heap = [(0, s)]
2while heap not empty:
3  k, u = heap.pop_min()
4  if inTree[u]: continue
5  inTree[u] = true; if u != s: mst.append((parent[u], u, k))
6  for (v, w) in adj[u]:
7    if not inTree[v] and w < key[v]:
8      key[v] = w; parent[v] = u; heap.push((w, v))

Implementations

1import heapq
2import math
3 
4 
5def prim(adj: list[list[tuple[int, float]]], root: int = 0) -> tuple[float, list[int]]:
6    """Prim's algorithm: grow one tree outward, always taking the cheapest
7    edge that leaves the tree. Returns (total, parent); total is -1 when the
8    graph is disconnected and parent[root] is -1."""
9    n = len(adj)
10 
111 · best[v] = cheapest known edge connecting v to the growing tree
12    best = [math.inf] * n
13    parent = [-1] * n
14    in_tree = [False] * n
15 
16    best[root] = 0
17    pq: list[tuple[float, int]] = [(0, root)]
18    total: float = 0
19    while pq:
202 · Take the cheapest edge leaving the tree; skip stale heap entries
21        w, u = heapq.heappop(pq)
22        if in_tree[u]:
23            continue
24        in_tree[u] = True
25        total += w
26 
273 · Adding u may improve the cheapest connection for its neighbours
28        for v, weight in adj[u]:
29            if not in_tree[v] and weight < best[v]:
30                best[v] = weight
31                parent[v] = u
32                heapq.heappush(pq, (weight, v))
33 
344 · A vertex left out of the tree means the graph was disconnected
35    if not all(in_tree):
36        return -1, []
37    return total, parent
38 
39 
405 · Dense graphs: the O(V^2) array scan beats the heap when E ~ V^2
41def prim_dense(w: list[list[float]]) -> float:
42    n = len(w)
43    best = [math.inf] * n
44    in_tree = [False] * n
45    best[0] = 0
46    total: float = 0
47    for _ in range(n):
48        u = min((v for v in range(n) if not in_tree[v]), key=lambda v: best[v])
49        if best[u] == math.inf:
50            return -1  # disconnected
51        in_tree[u] = True
52        total += best[u]
53        for v in range(n):
54            if not in_tree[v] and w[u][v] < best[v]:
55                best[v] = w[u][v]
56    return total
Walkthrough
  1. heapq supplies the priority queue, so Prim in Python is about a dozen lines of real logic.
  2. Tuples (weight, vertex) compare lexicographically, so the heap orders by weight and breaks ties deterministically by vertex id.
  3. if in_tree[u]: continue is the lazy-deletion guard that replaces decrease-key.
  4. all(in_tree) is the disconnection test, short-circuiting on the first False.
  5. prim_dense uses min(..., key=lambda v: best[v]) over a generator of non-tree vertices, which is the Pythonic spelling of the O(V) scan.
Complexity (this implementation)
time O(E log V) with heapq; O(V^2) for the dense variant · space O(V) for the lists, O(E) worst case for the heap

The min(..., key=...) scan is a Python-level loop, so prim_dense is much slower per operation than the C++ equivalent despite the same O(V^2).

Language notes
  • heapq is a min-heap, which is what Prim wants — no comparator inversion needed, unlike C++.
  • math.inf compares correctly against any number and never overflows, making it a cleaner sentinel than a large integer.
  • networkx.minimum_spanning_tree and scipy.sparse.csgraph.minimum_spanning_tree are the library answers for real workloads.
  • min(generator, key=...) raises ValueError on an empty generator, which is why prim_dense is bounded by range(n) rather than while.
Common mistakes in this language
  • Pushing (weight, vertex, payload) where the payload is not comparable, which raises TypeError on a weight-and-vertex tie.
  • Forgetting the in_tree stale check and adding a vertex twice, inflating the total.
  • Using sorted() on the frontier each round instead of a heap, which is O(E log E) per extraction.
Language differences that matter here
  • Heap orientation again separates the two languages that have one: heapq is a min-heap (what Prim wants directly), while std::priority_queue needs std::greater to stop building a maximum spanning tree.
  • JavaScript and TypeScript carry ~30 lines of inline binary heap that Python and C++ get from the standard library, which is most of the length difference between the four versions.
  • Sentinels: Infinity/math.inf saturate safely under comparison and addition, while C++ needs max/4 headroom to keep the same code overflow-free.
  • The disconnected case is reported as -1 in three languages and could be a discriminated union in TypeScript; Python and C++ would more idiomatically raise an exception or return std::optional.

Complexity

Best
O(E log V)
Average
O(E log V)
Worst
O(E log V)
Space
O(V + E)

Binary heap over adjacency list. Adjacency matrix with linear minimum scan: O(V²) — better when E ≈ V². Fibonacci heap: O(E + V log V).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Dense graphs or complete graphs defined by a distance function (points in the plane): O(V²) matrix Prim beats sorting V² edges.
  • The graph is given as adjacency lists and you already have a heap-based Dijkstra template — Prim is a two-line change.
  • You need the MST rooted at a particular node, or want to grow it incrementally from a seed.
Avoid it when
  • Sparse graphs given as an edge list — Kruskal's Algorithm is simpler and equally fast (O(E log E)), and gives extra information (components) for free.
  • Directed graphs — MST is undefined; the directed analogue (minimum arborescence, Chu-Liu/Edmonds) is a different algorithm.
  • Shortest paths — Prim keys by edge weight, not path length; the MST path between two nodes is generally not the shortest path.
  • Disconnected graphs when a spanning *forest* is required — Kruskal handles that naturally; Prim needs a restart per component.

Alternatives

Kruskal's AlgorithmDijkstra's Algorithm
Compare: Kruskal vs Prim

Common mistakes

  • Using dist[u] + w as the key (Dijkstra) instead of w — that yields a shortest-path tree, not an MST.
  • Adding an edge to the MST when it is pushed rather than when its node is popped — the pushed edge may later be beaten by a cheaper one.
  • Not skipping stale heap entries for nodes already in the tree, which double-counts weight.
  • Starting the matrix version by picking a node with key = ∞ when the graph is disconnected — check for it and report a forest.
  • Assuming the MST is unique; with equal weights several MSTs may exist (total weight is unique).

Interview patterns

  • Min cost to connect all points: complete graph on n ≤ 1000 points with Manhattan weights — O(n²) Prim without building an edge list.
  • Connecting cities with minimum cost: return -1 if the tree has fewer than n - 1 edges.
  • Explain Prim vs Dijkstra: same loop, different key.
  • Second-best MST / MST with a mandatory edge: build the MST, then argue via the cut and cycle properties.
Interview questions on this
Mock interviews

Example problems

Min Cost to Connect All Pointsmedium