Minimum spanning trees: Prim

What this chapter covers

The last five chapters all asked about paths — the cheapest way from here to there. This one asks a different question: how do you connect everything as cheaply as possible? Given a weighted graph of cities, houses, or circuit pins, find the set of edges that ties every node into one connected structure with the least total weight. The answer is a minimum spanning tree — spanning because it reaches every node, a tree because it has no redundant edges (exactly V−1 of them, no cycles), and minimum because no other spanning tree weighs less. Prim's algorithm builds one, and it's the third sibling of Dijkstra and A*: the same priority-queue traversal growing a frontier outward, with a single change — the heap is keyed on edge weight rather than distance from a source. This chapter builds it, watches the tree grow one cheapest-edge-at-a-time, and shows that "minimum" is worth a factor of three over just wiring things up however you reach them.

A bit of history

The algorithm has a tangled, much-rediscovered history. The Czech mathematician Vojtěch Jarník described it first, in 1930, to solve a concrete problem posed by an electrical engineer laying out an efficient power network in Moravia — so its origin, like so much of graph theory, is physical infrastructure. Robert Prim rediscovered it independently in 1957 while at Bell Labs working on minimizing the cost of connecting telephone exchanges, and Edsger Dijkstra rediscovered it again in 1959, in the very same paper family as his shortest-path work, which is why the two algorithms look so alike — they came from the same mind at the same time. It's properly the Jarník-Prim-Dijkstra algorithm, though "Prim's" stuck. That an efficient-network problem produced it three times over four decades tells you how fundamental it is: minimum spanning trees are the mathematical core of "connect these things cheaply," and that problem never stops mattering.

The intuition

Start with a single node in your tree and everything else outside. Look at all the edges that cross the boundary — that connect a node already in the tree to a node still outside — and pick the cheapest one. Add its outside endpoint to the tree. Now the boundary has moved: the newly added node brought its own edges, some of which cross the new boundary. Look again at all crossing edges, pick the cheapest, add its endpoint. Repeat until every node is in the tree. That's Prim's algorithm in full: always extend the tree by the single cheapest edge that grows it.

The priority queue is what makes "pick the cheapest crossing edge" fast. Each time you add a node, you push its edges (to still-outside neighbors) onto a min-heap keyed on weight; each step you pop the smallest, and if its far end is still outside, that's your next tree edge. Compare this to Dijkstra, which pushed onto the heap the total distance from the source; Prim pushes just the weight of the one edge. That's the entire difference. Dijkstra grows a tree of shortest paths — every node connected by its cheapest route back to the source. Prim grows a tree of cheapest connections — every node attached by the cheapest single edge available when it joined. Same outward-growing frontier, same heap, different key, different tree.

Complexity: how it scales

With a binary heap, Prim's is $O(E \log V)$: each edge is pushed and popped at most once ($\log V$ each), and each node is extracted once. With a Fibonacci heap it improves to $O(E + V \log V)$, which matters on very dense graphs, and a simple array-scan version (no heap) is $O(V^2)$, best when the graph is nearly complete. Space is $O(V)$ for the tree markers plus the heap. But the number that justifies the algorithm isn't its speed — it's how much cheaper its tree is than a spanning tree that ignores weight. The face-off measures exactly that: the total weight of Prim's minimum spanning tree versus an arbitrary spanning tree (the one a plain breadth-first traversal happens to build):

Both trees connect all the nodes with exactly the same number of edges — V−1 — so they're equally valid as connections. But on 400-node graphs the arbitrary breadth-first tree weighed about three times as much as the minimum spanning tree (roughly 6200 versus 2000). Same connectivity, triple the cost, purely because breadth-first search takes whatever edge first reaches a node while Prim's holds out for the cheapest one. In a real network — cable, pipe, road, circuit trace — that factor of three is money, or copper, or latency. "Minimum" isn't a mathematical nicety here; it's the difference between a cheap network and a wasteful one, and Prim's finds the cheap one in the same time BFS builds the wasteful one.

What it's good at, what it isn't

Prim's is the right tool for least-cost connection problems, especially on dense graphs where its edge-scanning frontier is efficient: designing networks (electrical grids, water and gas pipes, fiber and cable layouts, chip interconnect) to link every site at minimum total cost, and any problem that reduces to that. Minimum spanning trees also underpin clustering — remove the most expensive edges of an MST and the tree falls into tightly connected groups (single-linkage clustering is exactly this) — and they give fast approximations for hard problems like the traveling salesman. Prim's grows a single tree, which makes it a natural fit when you have a seed location to build outward from.

Where Prim's is less natural is sparse graphs, where Kruskal's edge-sorting approach (next chapter) is often simpler and competitive, and distributed or streaming settings, where Kruskal's independent edge decisions parallelize more easily than Prim's inherently sequential frontier growth. A minimum spanning tree also answers a specific question — cheapest connection — that people sometimes confuse with cheapest paths. The MST does not contain shortest paths between pairs of nodes: the tree route between two nodes can be far longer than their true shortest path. If you want short paths, that's Dijkstra; if you want cheap total connectivity, that's Prim. Same graph, different structures.

The data, or the inputs

The face-off runs on random connected weighted graphs and compares the total weight of Prim's minimum spanning tree against an arbitrary spanning tree built by breadth-first search — the same nodes, the same V−1 edge count, isolating the effect of choosing edges by weight. Correctness is cross-checked against Kruskal's algorithm (the independent MST method of the next chapter): on hundreds of random graphs Prim's total weight must equal Kruskal's, and the result must have V−1 edges spanning every node. The animation runs Prim on a small weighted graph, drawing the cut each step — dashed blue edges are candidates crossing from tree to outside — and lighting up the cheapest one as it's chosen.

Build it, one function at a time

The whole algorithm — a heap of crossing edges, add the cheapest, push the new node's edges:

def prim(adj, n, start=0):
    """Grow a minimum spanning tree from `start`. `adj[u]` is a list of (neighbor, weight).
    Keep a min-heap of candidate edges (weight, from_tree, to_node) that cross from the tree
    to the outside. Repeatedly pull the cheapest crossing edge; if its far end is still
    outside, add that edge to the tree and push the new node's own edges as fresh candidates.
    O(E log V). Returns (mst_edges, total_weight)."""
    in_tree = [False] * n
    in_tree[start] = True
    mst_edges = []
    total = 0
    pq = [(w, start, v) for v, w in adj[start]]   # edges leaving the start node
    heapq.heapify(pq)
    while pq and len(mst_edges) < n - 1:
        w, a, b = heapq.heappop(pq)
        if in_tree[b]:
            continue                              # b already attached — stale crossing edge
        in_tree[b] = True                         # attach b to the tree via the cheapest edge
        mst_edges.append((a, b, w))
        total += w
        for c, wc in adj[b]:                       # b's edges are new candidates across the cut
            if not in_tree[c]:
                heapq.heappush(pq, (wc, b, c))
    return mst_edges, total

And the quantity it minimizes, for reference:

def spanning_tree_weight(edges):
    """Sum the weights of a set of (u, v, w) tree edges — the quantity a minimum spanning
    tree minimizes."""
    return sum(w for _, _, w in edges)

Watch it work

Here's Prim growing a minimum spanning tree from node 0. Green nodes are in the tree; dark nodes are still outside; orange marks the node just added. The edges tell the story of the cut: dashed blue edges cross from the tree to the outside — they're the candidates — grey edges are entirely outside the tree, and green edges are the tree itself. Each step, Prim pops the cheapest crossing edge (it flashes orange) and adds its outside endpoint, which shifts the boundary and reveals new candidates. Watch the running total climb by the smallest possible amount every step — never edge weight 6 when a weight-1 edge still crosses the cut — until all seven nodes hang together on six edges of total weight 15, the cheapest connection possible:

The complete code

The from-scratch tab is Prim with its priority queue; the library tab is Kruskal — the other MST algorithm, used here as the independent reference Prim's total is checked against — plus the weight-ignoring BFS spanning tree from the face-off, and the networkx/scipy calls you'd use in production. Flip between them.

"""Prim's algorithm — connect every node of a weighted graph using the cheapest possible
total length of edges, with no cycles. That subgraph is a MINIMUM SPANNING TREE: spanning
(it touches every node), a tree (V−1 edges, no cycles), and minimum (no other spanning tree
weighs less). It's the answer to "wire up all these houses / cities / components as cheaply
as I can."

Prim's is A* and Dijkstra's twin. It grows a single tree outward from a start node using a
priority queue, and the only thing that changes is WHAT the heap is keyed on. Dijkstra put
g(n) — the total distance from the source — on the heap. Prim puts just the WEIGHT OF THE
EDGE that would attach a new node to the tree. So instead of "which node is closest to the
start," Prim repeatedly asks "which node is cheapest to connect to the tree I have so far,"
adds it, and repeats. Same heap-driven frontier, one word changed, and a shortest-path
traversal becomes a minimum-spanning-tree builder.
"""
import heapq


# region: prim
def prim(adj, n, start=0):
    """Grow a minimum spanning tree from `start`. `adj[u]` is a list of (neighbor, weight).
    Keep a min-heap of candidate edges (weight, from_tree, to_node) that cross from the tree
    to the outside. Repeatedly pull the cheapest crossing edge; if its far end is still
    outside, add that edge to the tree and push the new node's own edges as fresh candidates.
    O(E log V). Returns (mst_edges, total_weight)."""
    in_tree = [False] * n
    in_tree[start] = True
    mst_edges = []
    total = 0
    pq = [(w, start, v) for v, w in adj[start]]   # edges leaving the start node
    heapq.heapify(pq)
    while pq and len(mst_edges) < n - 1:
        w, a, b = heapq.heappop(pq)
        if in_tree[b]:
            continue                              # b already attached — stale crossing edge
        in_tree[b] = True                         # attach b to the tree via the cheapest edge
        mst_edges.append((a, b, w))
        total += w
        for c, wc in adj[b]:                       # b's edges are new candidates across the cut
            if not in_tree[c]:
                heapq.heappush(pq, (wc, b, c))
    return mst_edges, total
# endregion


# region: total_weight
def spanning_tree_weight(edges):
    """Sum the weights of a set of (u, v, w) tree edges — the quantity a minimum spanning
    tree minimizes."""
    return sum(w for _, _, w in edges)
# endregion

"""The library counterpart, an independent reference, and the contrast. In production a
minimum spanning tree comes from networkx or scipy:

    import networkx as nx
    T = nx.minimum_spanning_tree(G, weight="weight")   # Kruskal by default
    total = T.size(weight="weight")

To check Prim without a third-party dependency, the trace generator uses KRUSKAL below —
the *other* classic MST algorithm (next chapter), which builds the tree a completely
different way: sort all edges cheapest-first and add each one that doesn't form a cycle,
using union-find. Prim grows one tree from a seed; Kruskal merges a forest. They can pick
different trees, but the total weight of a minimum spanning tree is the same however you
build it — so Kruskal's total is the ground truth for Prim's.

`bfs_spanning_tree` is the contrast: *a* spanning tree that ignores weight, to show how much
"minimum" actually saves over just connecting everything however you happen to reach it.
"""
from collections import deque


# region: kruskal
def kruskal(adj, n):
    """MST by Kruskal's method: sort edges ascending, add any that joins two different
    components (union-find), skip any that would close a cycle. Independent of Prim, so it's
    the reference for Prim's total weight."""
    edges = set()
    for u in range(n):
        for v, w in adj[u]:
            edges.add((w, min(u, v), max(u, v)))
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total, picked = 0, []
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            total += w
            picked.append((u, v, w))
    return picked, total
# endregion


# region: arbitrary
def bfs_spanning_tree(adj, n, start=0):
    """*A* spanning tree — the one BFS happens to build, taking whatever edge first reaches
    each node, weight be damned. Same node count, same connectivity, but no attempt to
    minimize total weight. The baseline a minimum spanning tree improves on."""
    seen = [False] * n
    seen[start] = True
    q = deque([start])
    total, picked = 0, []
    while q:
        u = q.popleft()
        for v, w in adj[u]:
            if not seen[v]:
                seen[v] = True
                total += w
                picked.append((u, v, w))
                q.append(v)
    return picked, total
# endregion

Scratch vs library

The comparison worth drawing here is Prim against its own family. It's Dijkstra's twin — the same priority-queue traversal, differing only in the heap key — which is a lovely illustration that a small change to a familiar algorithm can answer a completely different question. And it's Kruskal's rival: two algorithms that build minimum spanning trees by opposite strategies (Prim grows one tree from a seed; Kruskal merges a forest of many), yet always arrive at the same total weight, because both are just the cut property applied through different cuts. That the correctness check can validate Prim against Kruskal — two independent methods agreeing — is itself the lesson: when a problem has a well-defined optimum, different correct algorithms converge on it, and cross-checking one against another is a stronger test than either against itself. In production you'd call networkx.minimum_spanning_tree or scipy.sparse.csgraph.minimum_spanning_tree; building Prim yourself is what makes "it's Dijkstra with a different key" something you've seen rather than been told.

Where you'll actually meet it

Minimum spanning trees are the mathematics of cheap connection, so Prim's runs wherever networks are designed to link everything at least cost: electrical grid and telecom layout (its original purpose), water and gas pipe networks, fiber and cable routing, and chip interconnect and PCB trace minimization in hardware design. It's a workhorse of clustering — single-linkage hierarchical clustering builds an MST and cuts its heaviest edges, and MST-based methods segment images and group data. It gives a 2-approximation for the metric traveling-salesman problem, seeding route optimization. It appears in network reliability analysis, in maze generation (a random-weight MST is a perfect maze), and in handwriting and gesture recognition. Anywhere the task is "connect all of these as cheaply as possible," a minimum spanning tree is the answer and Prim's is one of the two ways to build it.

Takeaways

Prim's algorithm builds a minimum spanning tree — the cheapest edge set connecting every node — by repeatedly adding the lowest-weight edge that crosses from the tree to the outside, using a priority queue, in $O(E \log V)$. It's Dijkstra with one change, the heap keyed on edge weight instead of distance from a source, and its greedy rule is provably optimal via the cut property: the cheapest edge across any cut belongs to some minimum spanning tree. Its tree is a factor of several cheaper than an arbitrary spanning tree, but it is not a shortest-path tree — cheap total connection is a different structure from short individual routes.

The next chapter builds the same minimum spanning tree by the opposite strategy. Kruskal's algorithm ignores any starting point, sorts every edge cheapest-first, and adds each one that doesn't create a cycle — merging a forest of separate trees into one. It needs a fast way to ask "would this edge close a cycle?", which is exactly the union-find structure from the trees tier, making Kruskal a satisfying reunion of two threads of this book.