Prim's Algorithm

#How does it work?

Prim's algorithm also finds a minimum spanning tree, but in a different way from Kruskal: instead of sorting edges it grows the tree from a start node.

At every step it picks the cheapest edge from a node inside the tree to a node outside, and that node joins the tree. For each outside node it keeps its "cheapest link to the tree" (key) and finds the smallest with a priority queue.

It is structured almost exactly like Dijkstra; only the compared value differs. Dijkstra looks at the total distance from the start (dist[u] + w), Prim only at the edge weight (w). The total weight is the same whichever node you start from.

#Try it yourself

#Step by step

1. 01Set key[start] = 0 and every other key to ∞.
2. 02Pick the outside node u with the smallest key and add it to the tree.
3. 03For each outside neighbour v of u with edge weight w < key[v], set key[v] = w and prev[v] = u.
4. 04Repeat until every node is in the tree; the prev[] edges form the tree.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

import heapq

EDGES = [(1, 2, 4), (1, 3, 1), (2, 4, 5), (2, 5, 2), (3, 5, 2), (3, 6, 4), (4, 7, 3), (5, 7, 6), (6, 7, 1)]
graph = {v: [] for v in range(1, 8)}
for a, b, w in EDGES:
    graph[a].append((b, w))
    graph[b].append((a, w))


def prim(start: int):
    in_tree, order, total = set(), [], 0
    heap = [(0, start)]  # (cheapest known link to the tree, node)
    while heap:
        w, u = heapq.heappop(heap)
        if u in in_tree:
            continue  # an outdated, more expensive link
        in_tree.add(u)
        order.append(u)
        total += w
        for v, weight in graph[u]:
            if v not in in_tree:
                heapq.heappush(heap, (weight, v))
    return order, total


order, total = prim(1)
print(" ".join(map(str, order)))  # the order nodes joined the tree
print(total)

#Complexity

On dense graphs (E ≈ V²) the heap-free array version, O(V²), beats Kruskal's O(E log E) = O(V² log V). On sparse graphs Kruskal is usually simpler and faster. If the graph isn't connected, Prim only spans the start's part.

#When to use it?

MSTs of dense graphs (e.g. a network where every city can connect to every other), maze generation (Prim with random weights makes nice mazes) and networks that grow out from one hub suit Prim.

#Practice

Log in to answer questions and save your progress.