Prim's Minimum Spanning Tree, in depth: the cut property, lazy and eager heaps, the dense-graph version and the bugs that break it

The problem, stated precisely

Take a connected, undirected graph with V vertices, E edges and a real weight on each edge. A spanning tree is a subset of exactly V-1 edges that connects all vertices with no cycle. A minimum spanning tree (MST) is a spanning tree whose total weight is as small as possible. Four facts shape everything that follows.

• If all weights are distinct, the MST is unique. With ties there may be several, but they all have the same total weight.
• Negative weights are fine. Unlike shortest paths, an MST only compares edges with each other, so adding a constant to every weight does not change which tree is minimal.
• If the graph is disconnected there is no spanning tree. The natural generalisation is a minimum spanning forest: one MST per connected component.
• The definition is for undirected graphs. The directed version, a minimum spanning arborescence, needs a different algorithm (Chu-Liu/Edmonds); running Prim on a directed graph gives a wrong answer.

Why greedy works: the cut property

A cut splits the vertices into two non-empty groups S and V-S. An edge crosses the cut if it has one end in each group. The cut property says: for any cut, a lightest crossing edge belongs to some MST, and if it is the unique lightest, it belongs to every MST.

The proof is an exchange argument. Take an MST T that does not contain the lightest crossing edge e = (u, v). Adding e to T creates exactly one cycle. That cycle goes from u to v inside T and must cross the cut at least once more, through some edge f. Swap them: T - f + e is still a spanning tree, and since w(e) ≤ w(f) its weight is no larger. So a minimum tree containing e exists.

Prim applies this directly. At every step, let S be the vertices already in the tree. The cheapest edge leaving S is a lightest crossing edge of the cut (S, V-S), so adding it keeps the partial tree inside some MST. After V-1 steps the tree spans everything and is minimal. The same property justifies Kruskal and Boruvka; they just choose cuts differently.

The algorithm

Prim keeps, for every vertex outside the tree, a key: the weight of the cheapest edge connecting it to the tree so far, and a parent: the tree vertex at the other end of that edge. Each step moves the vertex with the smallest key into the tree, records the edge (parent, vertex), and then looks at the new vertex's neighbours: any neighbour outside the tree whose connecting edge is cheaper than its current key gets a new key and parent. The data structure question is only how to find the smallest key quickly, and that is where the implementations differ.

Worked example, traced by hand

The graph below has six vertices and nine edges. Start at A.

Total weight 2 + 1 + 5 + 2 + 3 = 13. Notice step 3: B's key dropped from 4 to 1 because C, which joined the tree after B's first key was set, offered a cheaper edge. Notice step 4 as well: B-D with weight 5 is chosen even though there are lighter edges in the graph, because it is the lightest edge crossing from {A, B, C} to {D, E, F}. As a check, Kruskal sorts the edges, takes B-C 1, A-C 2, D-E 2 and E-F 3, rejects A-B 4 because it closes a cycle, then takes B-D 5: the same tree.

Implementation 1: lazy Prim with a binary heap

The simplest fast version pushes every candidate edge onto a heap and ignores stale entries when they surface. A vertex may appear in the heap several times with different weights; only the first pop counts.

import heapq
from collections import defaultdict

def prim_lazy(n, edges, root=0):
    """n vertices 0..n-1, edges as (u, v, w). Returns (tree_edges, total)."""
    adj = defaultdict(list)
    for u, v, w in edges:
        adj[u].append((w, v))
        adj[v].append((w, u))
    in_tree = [False] * n
    tree, total = [], 0
    heap = [(0, root, -1)]                  # (edge weight, vertex, parent)
    while heap and len(tree) < n - 1:
        w, v, parent = heapq.heappop(heap)
        if in_tree[v]:
            continue                        # stale: v already joined by a cheaper edge
        in_tree[v] = True
        if parent != -1:
            tree.append((parent, v, w))
            total += w
        for w2, x in adj[v]:
            if not in_tree[x]:
                heapq.heappush(heap, (w2, x, v))
    if len(tree) != n - 1:
        raise ValueError("graph is disconnected; use a spanning forest")
    return tree, total

Each edge is pushed at most twice, so the heap holds O(E) entries and the running time is O(E log E), which equals O(E log V) because E is at most V squared. Memory is O(E) for the heap. In Python, heapq compares whole tuples, so ties fall through to comparing vertex ids. That is fine for integers, but if vertices are objects that do not support ordering you get a TypeError; insert a running counter as the second tuple element to break ties instead.

Implementation 2: eager Prim with decrease-key

The eager version keeps at most one entry per vertex in an indexed priority queue and lowers its key in place, so the heap never exceeds V entries.

PRIM-EAGER(G, root):
    for each vertex v: key[v] = +inf, parent[v] = nil
    key[root] = 0
    PQ = indexed min-priority queue over all vertices, keyed by key[]
    while PQ not empty:
        v = PQ.extract_min()
        if key[v] == +inf: start a new tree here (graph is disconnected)
        mark v in tree
        for each edge (v, x, w):
            if x not in tree and w < key[x]:
                key[x] = w; parent[x] = v
                PQ.decrease_key(x, w)

With a binary indexed heap this is O(E log V) time and O(V) heap memory. With a Fibonacci heap, where decrease-key is amortised O(1), the bound becomes O(E + V log V), which is better on paper for dense graphs. In practice Fibonacci heaps have large constants and poor cache behaviour, and the lazy binary-heap version usually wins on real hardware unless the graph is very large and very dense. Python's standard library has no decrease-key, which is why the lazy version is idiomatic there; Java and C++ implementations often use an indexed heap. How heap operations cost what they cost is covered in heap operations.

Implementation 3: the O(V squared) array version for dense graphs

When the graph is dense, for example a complete graph built from points in the plane, E is about V squared and a heap only adds overhead. Scanning an array of keys for the minimum costs O(V) per step and O(V squared) overall, which matches the size of the input.

def prim_dense(W):
    """W is an n x n matrix; W[i][j] = weight, or float('inf') if no edge."""
    n, INF = len(W), float("inf")
    key, parent, used = [INF] * n, [-1] * n, [False] * n
    key[0], total = 0, 0
    for _ in range(n):
        v = min((i for i in range(n) if not used[i]), key=key.__getitem__)
        if key[v] == INF:
            raise ValueError("graph is disconnected")
        used[v] = True
        total += key[v]
        for u in range(n):
            if not used[u] and W[v][u] < key[u]:
                key[u], parent[u] = W[v][u], v
    return total, parent

This version has no heap, no stale entries and a tiny memory footprint, and its inner loop is a sequential scan that runs well on modern CPUs. For a few thousand points with all pairwise distances it is usually the fastest option, and it is simple enough to verify by inspection.

The most common bug: copying Dijkstra

Prim and Dijkstra have the same skeleton, which makes it tempting to adapt one into the other. The difference is a single line, and getting it wrong produces a tree that spans the graph but is not minimal: a shortest-path tree instead.

# Dijkstra relaxation (shortest paths): priority is the whole path length
if dist[v] + w < dist[x]:
    dist[x] = dist[v] + w

# Prim relaxation (spanning tree): priority is the single connecting edge
if not in_tree[x] and w < key[x]:
    key[x] = w
    parent[x] = v

In the example, the Dijkstra version ranks F by its shortest distance from A, 13, instead of by the weight 3 of the edge that would join it, and in general it chooses different edges whenever a path that is short overall competes with a single light edge. On this particular graph the shortest-path tree from A happens to equal the MST, so the buggy version returns the right answer here, which is why one hand-worked example is not a test. Take three vertices with A-B 1, B-C 1 and A-C 1.5: the MST is A-B plus B-C, total 2, while the Dijkstra version picks A-B and A-C, total 2.5. Both outputs have V-1 edges and look plausible, so only a total-weight comparison against a second algorithm reliably catches it. Dijkstra's own invariants are explained in Dijkstra's algorithm.

Prim, Kruskal and Boruvka compared

A practical rule: if you have an adjacency structure or a distance matrix, use Prim; if you have a flat edge list, use Kruskal; if you need to parallelise, use Boruvka, whose rounds are independent per component.

Edge cases and failure modes

• Disconnected graph. The heap empties early and the tree has fewer than V-1 edges. Either raise, as the code above does, or loop over unvisited vertices to build a spanning forest.
• Directed edges. Prim assumes symmetry; adding only one direction to the adjacency list silently produces a wrong tree.
• Parallel edges and self-loops. Harmless: the heap picks the cheapest parallel edge and self-loops are never chosen, but deduplicating saves heap work.
• Floating-point ties. Two correct implementations may return different trees whose totals differ in the last bits. Compare totals with a tolerance, not equality.
• Overflow. In fixed-width languages the total of many large weights can overflow a 32-bit integer; use 64-bit accumulators.
• Starting vertex. It does not change the total weight, only the order of additions; tests that assert a specific edge order are testing an implementation detail.

Where Prim shows up in practice

Network design is the direct application: cabling, pipelines and road networks where any connection works and cost is additive. In machine learning, single-linkage clustering is exactly an MST with its k-1 heaviest edges removed, leaving k clusters, and some density-based clustering methods build an MST over a transformed distance. Graph-based image segmentation merges pixels along MST edges. For the metric travelling salesman problem, walking an MST in preorder and skipping repeated vertices gives a tour at most twice the optimum, a classic approximation. In all of these the dense, all-pairs form appears often, which is where the array version earns its place.

Testing an implementation

Generate random connected graphs of a few dozen vertices, run Prim and an independent Kruskal, and assert equal totals within tolerance. Then assert structural properties: exactly V-1 edges, every vertex reached, no cycle (a union-find over the result detects one), and every chosen edge present in the input. Add hand-built cases for a single vertex, two vertices, all-equal weights, negative weights and a disconnected graph. With distinct random weights, also assert the edge sets are identical, since the MST is then unique.

What to do next

1. Implement lazy Prim and reproduce the worked example's total of 13 and its five edges.
2. Write Kruskal with union-find and a random-graph test that compares totals across both.
3. Add the O(V squared) version and time all three on sparse graphs and on complete graphs of 2,000 points.
4. Deliberately introduce the Dijkstra relaxation bug and confirm your tests catch it.
5. Extend Prim to return a spanning forest on disconnected input.
6. Use your MST for single-linkage clustering on a small 2D dataset by removing the k-1 heaviest edges.