🎓 A1Learner
🔍

DSA Prim's Algorithm

Prim's algorithm builds a minimum spanning tree by growing one tree outward from a start vertex. At each step it takes the cheapest edge that leads out of the tree.

The cheapest way out

The tree starts as node 0 alone in this sketch. Its cheapest outgoing edge joins node 1 next.

frontier = [(6, 0, 3), (2, 0, 1)]
frontier.sort()
print("cheapest outgoing edge:", frontier[0])
print("it joins node", frontier[0][2], "to the tree")

Heap order settles ties

Two entries here share the weight 5. The entry with the smaller first endpoint leaves the heap first.

import heapq

heap = []
heapq.heappush(heap, (5, 1, 4))
heapq.heappush(heap, (2, 0, 1))
heapq.heappush(heap, (5, 0, 3))
print("pop order:")
while heap:
    print(heapq.heappop(heap))

Outgoing means one end in

Only edges crossing the tree boundary count as outgoing. The edge between nodes 1 and 2 stays invisible until one end joins.

in_tree = {0}
edges = [(0, 1, 2), (0, 3, 6), (1, 2, 3)]
outgoing = [(w, u, v) for u, v, w in edges
            if (u in in_tree) != (v in in_tree)]
print("tree:", sorted(in_tree))
print("outgoing edges:", sorted(outgoing))

Example

import heapq

edges = [(0, 1, 2), (1, 2, 3), (2, 3, 4), (1, 4, 5),
         (0, 3, 6), (2, 4, 7), (1, 3, 8), (3, 4, 9)]
graph = {i: [] for i in range(5)}
for u, v, w in edges:
    graph[u].append((w, u, v))
    graph[v].append((w, v, u))

in_tree = {0}
heap = list(graph[0])
heapq.heapify(heap)
pushes = len(heap)
total = 0
taken = 0
stale = 0
while heap:
    w, u, v = heapq.heappop(heap)
    if v in in_tree:
        stale += 1
        print(w, "to", v, "skipped: already in tree")
        continue
    in_tree.add(v)
    total += w
    taken += 1
    print(u, "-", v, "weight", w, "taken, total", total)
    for entry in graph[v]:
        if entry[2] not in in_tree:
            heapq.heappush(heap, entry)
            pushes += 1
print("MST cost:", total, "edges taken:", taken)
print("heap pushes:", pushes, "stale pops:", stale)
print("Kruskal cost for the same graph: 14, match:", total == 14)

Key points

  • A minimum spanning tree is the cheapest edge set connecting every vertex without cycles.
  • An outgoing edge is an edge with exactly one end inside the tree.
  • A heap holds the known outgoing edges with the cheapest on top.
  • Heap entries compare by weight first, then by first endpoint, then by second.
  • A popped edge whose far end already joined the tree is stale.
  • Stale edges are skipped, and the growth continues with the next entry.

In this example, Prim's algorithm grows the tree from node 0 through the same four cheap edges as Kruskal's algorithm. Four stale heap entries are popped and skipped along the way. The total is 14, which matches the Kruskal total for this identical graph.

Note

Prim and Kruskal may pick different edges on ties, but their total costs must agree.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

The heap pops an edge whose far end is already inside the tree. What happens next?