Algorithm Guidecomplexity: O(E log V)

Prim MST

Starts from one node and grows a minimum spanning tree by adding the cheapest edge connected to the tree, one at a time. It manages candidate edges with a priority queue and grows in a different order than Kruskal, but reaches the same MST.

01Prim MST

Explore How It Works

Starting Prim. Set source node A's key to 0 and the rest to ∞. Grow the tree one node at a time from A.

Add A to the tree and update its neighbors' keys. B is 1, C is 3 — the edge weights from A.

Add B(1), the smallest key, to the tree via edge AB. From B, C's key drops 3→2 and D becomes 5.

Add C(2), the smallest key, via edge BC. From C, D's key drops 5→4 and E becomes 7.

Add D(4), the smallest key, via edge CD. From D, E's key drops 7→6.

Finally add E(6) via edge DE. Every node is now in the tree, completing the MST.

Done · MST = AB + BC + CD + DE, total weight 13. It grew in a different order than Kruskal but reaches the same result.

Live Python

1import heapq

2def prim(graph, start):

# visited = {A}

3 visited = {start}

4 pq = [(w, start, v) for v, w in graph[start]]

5 heapq.heapify(pq)

6 mst, total = [], 0

7 while pq:

8 w, u, v = heapq.heappop(pq)

9 if v in visited:

10 continue

11 visited.add(v)

12 mst.append((u, v)); total += w

13 for nxt, w2 in graph[v]:

14 if nxt not in visited:

15 heapq.heappush(pq, (w2, v, nxt))

16 return mst, total

1 / 7

02 Understand It Simply

For Everyone

🔑How It Works

Starts at one vertex and repeatedly adds the lightest edge that attaches a new vertex to the tree built so far.

💡In Plain Words

Grows a minimum spanning tree by adding the cheapest edge connected to it, one at a time.

A different order than Kruskal, but the same result.

📍Where It's Used

–Least-cost connected networks
–MST of dense graphs

03 Python Implementation

A clean, readable reference implementation of the core logic of Prim MST.

core_implementation.py

import heapq

def prim(graph, start):
    visited = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    mst, total = [], 0
    while pq:
        w, u, v = heapq.heappop(pq)
        if v in visited:
            continue
        visited.add(v)
        mst.append((u, v))
        total += w
        for nxt, w2 in graph[v]:
            if nxt not in visited:
                heapq.heappush(pq, (w2, v, nxt))
    return mst, total