Prim's Algorithm: A Hands-On Visual Guide with Python

The Story That Explains Prim's Algorithm

Prim's algorithm finds the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph: the cheapest set of edges that connects all vertices with no cycles. It was first described by Vojtěch Jarník in 1930, then independently by Robert C. Prim in 1957 and Edsger Dijkstra in 1959 — which is why you'll sometimes see it called the Jarník–Prim algorithm.

The Foundation — What Is a Minimum Spanning Tree?

Before the algorithm, you need three definitions. A spanning tree of a graph with V vertices is a set of edges that touches every vertex, stays connected, and contains no cycle — which means it always has exactly V − 1 edges. A graph can have many spanning trees; the minimum spanning tree is simply the one whose edge weights add up to the smallest total.

Why Greedy Works — The Cut Property

Prim's is a greedy algorithm: it never reconsiders a choice. The reason it still lands on the optimal answer is a small piece of graph theory called the cut property.

The Algorithm in Five Steps

Hands-On: Watch Every Line of Code Build the Tree

This is the heart of the tutorial. Below, the graph on the left and the Python on the right are wired together. Press Play (or step manually) and watch the highlighted line of code drive exactly one change in the graph: the active line is the task happening on the canvas. Candidate edges glow blue, the edge under consideration pulses amber, accepted MST edges turn solid green, and cycle-forming edges flash red before being discarded.

Python Implementation

Heap-Based Prim — O(E log V)

This is the implementation the visualiser above animates, using Python's built-in heapq min-heap so the cheapest candidate edge is always popped first. Each commented line corresponds to one highlighted step in the animation.

import heapq

def prim(graph, start):
    visited = {start}                      # the tree starts at the source vertex
    mst, total = [], 0                    # chosen edges + running cost
    frontier = []                          # a min-heap of candidate edges

    for nbr, w in graph[start]:            # seed the heap with the source's edges
        heapq.heappush(frontier, (w, start, nbr))

    while frontier:                        # keep going while candidates remain
        w, u, v = heapq.heappop(frontier)  # cheapest edge leaving the tree
        if v in visited:                   # both ends already in? skip the cycle
            continue
        visited.add(v)                     # bring v into the tree
        mst.append((u, v, w))             # lock in the chosen edge
        total += w                         # grow the total cost
        for nbr, w2 in graph[v]:          # expand the frontier from v
            if nbr not in visited:
                heapq.heappush(frontier, (w2, v, nbr))

    return mst, total                     # V-1 edges + minimum cost

Running It on Our Six-Town Graph

graph = {
    'A': [('B', 4), ('F', 6), ('E', 8)],
    'B': [('A', 4), ('F', 2), ('C', 5)],
    'C': [('B', 5), ('F', 3), ('D', 4)],
    'D': [('C', 4), ('F', 7), ('E', 3)],
    'E': [('D', 3), ('F', 5), ('A', 8)],
    'F': [('A', 6), ('B', 2), ('C', 3), ('D', 7), ('E', 5)],
}

edges, cost = prim(graph, 'A')
for u, v, w in edges:
    print(f"{u} -- {v}  (weight {w})")
print("Total MST cost:", cost)

Dense-Graph Variant — O(V²) with an Adjacency Matrix

When the graph is dense (close to every-pair-connected), a plain array scan beats a heap. No priority queue, just a key[] array holding the cheapest known edge weight to reach each vertex.

import math

def prim_dense(W):                       # W is a V x V weight matrix (inf = no edge)
    n = len(W)
    key    = [math.inf] * n               # cheapest edge reaching each vertex
    parent = [-1] * n                    # which tree-vertex it attaches to
    in_mst = [False] * n
    key[0] = 0                            # start from vertex 0

    for _ in range(n):
        u = min((k, i) for i, k in enumerate(key)
                if not in_mst[i])[1]   # pick closest non-tree vertex
        in_mst[u] = True
        for v in range(n):                 # relax neighbours of u
            if not in_mst[v] and W[u][v] < key[v]:
                key[v], parent[v] = W[u][v], u

    return parent, sum(key)

The Run, Traced Step by Step

Here is exactly what the animation does, written out as a table. Starting at A, the heap always serves the cheapest crossing edge. Cycle-forming edges are popped but skipped.

Time & Space Complexity

Benefits of Prim's Algorithm

Real-World Use Cases

Prim vs Kruskal — Side by Side

Golden Rules