Visualizer CodeViz · Algorithms, visualized

Part II · Minimum spanning trees · week 3

Prim's MST (lazy)

Keep one growing tree and always add the cheapest edge leaving it. A priority queue supplies that edge; stale entries are simply thrown away.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

timeO(E log E) lazy
eager versionO(E log V) with an indexed PQ
data structuremin priority queue
greedyprovably optimal

Reference: Sedgewick & Wayne, §4.3; Jarník 1930, Prim 1957.

Prim's MST (lazy) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

import heapq

class LazyPrimMST:
    # Grow ONE tree from vertex 0. Every edge with an endpoint in the tree
    # goes on a min-heap. Pop the smallest; if both endpoints are now in
    # the tree the edge is obsolete (it no longer crosses the cut), so
    # discard it. That laziness is what keeps the code short.

    def __init__(self, graph):
        self.marked = [False] * graph.V   # marked = in the tree
        self.mst = []
        self.weight = 0.0
        self.pq = []
        self._visit(graph, 0)
        while self.pq and len(self.mst) < graph.V - 1:
            weight, v, w = heapq.heappop(self.pq)
            if self.marked[v] and self.marked[w]:
                continue                  # obsolete edge: skip it
            self.mst.append((v, w, weight))
            self.weight += weight
            if not self.marked[v]:
                self._visit(graph, v)
            if not self.marked[w]:
                self._visit(graph, w)

    def _visit(self, graph, v):
        self.marked[v] = True             # v joins the tree ...
        for w, weight in graph.adj(v):
            if not self.marked[w]:        # ... so its edges may now cross
                heapq.heappush(self.pq, (weight, v, w))

Why it works

One tree, always connected

Kruskal's forest is a scattering of fragments that finally merge; Prim's is a single tree that grows one vertex at a time. Both are the cut property in action — Prim's cut is always tree vertices versus the rest, and the cheapest crossing edge is always safe to add.

What “lazy” means

When a vertex joins the tree, some edges already on the heap stop crossing the cut (both their endpoints are now inside). The lazy version does not try to remove them; it lets them sit there and discards them when they surface. That costs extra space and a few wasted pops, in exchange for a much simpler program. Watch the frames labelled obsolete.

The eager version

The eager Prim keeps at most one entry per vertex — the cheapest known edge connecting it to the tree — in an indexed priority queue that supports decrease_key. That drops the heap size from E to V and the running time to O(E log V). Same idea, and the same data-structure upgrade Dijkstra needs.

Prim or Kruskal?

Both are O(E log E)-ish and both are used. Prim is better on dense graphs (its cost tracks V) and when the graph is only available incrementally; Kruskal is better on sparse graphs and when the edges are already sorted — then it is nearly linear. Neither is asymptotically optimal: Chazelle's algorithm runs in O(E α(E,V)) and whether a truly linear-time MST algorithm exists is still open.

What to try in the animation

Same graph as Kruskal's, same answer (weight 1.81) — but built in a completely different order. Watch the tree stay connected the whole way.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Prim's MST (lazy) in the player →

The rest of Minimum spanning trees