43224315423ABCDEFGH
AlgoPlus//graph / prim
Read the theory

Prim's MST

Grow one tree by absorbing the cheapest frontier edge.

Stability
—
In-Place
—
Space Complexity
—
Avg Time
—
Source
Legend
Current
Frontier
Visited
Path / MST
AI Tutor Workspace
—
In a nutshell
Prim's algorithm builds a minimum spanning tree — the cheapest set of edges that connects every vertex with no cycles. Start from any vertex and repeatedly add the lowest-weight edge linking the growing tree to a vertex not yet in it, until all are joined. It grows one connected blob outward, much like Dijkstra but judging each edge by its own weight rather than by total distance.
Ready
Press play to begin the cinematic walkthrough.
Grow a single tree outward, always absorbing the cheapest edge that touches new territory.
Key terms
Go deeper in the lesson
Read the full theory, intuition & complexity for Prim's MST.
Code Simulator
▼
1
def prim(graph, start):
2
    visited = {start}
3
    edges = [(w, start, v) for v, w in graph[start]]
4
    heapify(edges)
5
    while edges:
6
        w, u, v = heappop(edges)  # Settle edge
7
        if v not in visited:
8
            visited.add(v)  # Absorb node
9
            for nv, nw in graph[v]:
10
                heappush(edges, (nw, v, nv))
Why Python? · Readable first, fast second

Dynamically typed and interpreted — every comparison and swap is dispatched by the interpreter at run time, so tight loops run roughly 10–100× slower than compiled C/C++. Unbeatable for learning the idea with the least code; not what you reach for when the inner loop is the bottleneck.