Prim's Algorithm Visualizer

How it works

1. Start the tree with one node s and push all of its edges into a min-priority queue.
2. Pop the cheapest edge. If its far end is already in the tree, discard it — it no longer leaves the tree.
3. Otherwise add the edge and its far end b to the tree.
4. Push every edge from b to a node that is still outside the tree.
5. Repeat until all V nodes are in the tree. If the queue empties first, the graph is disconnected and only the start's component is spanned.

Why the cheapest crossing edge is safe

At every moment the nodes are split into two groups: the tree and the rest. By the cut property, the cheapest edge crossing that split belongs to some minimum spanning tree, so adding it can never be a mistake. Prim simply applies this rule V − 1 times, each time to the cut between the growing tree and the remaining nodes.

Because the tree is always connected, Prim never needs union-find: an edge can only close a cycle if both of its ends are already in the tree, and those edges are exactly the ones it discards.

Worked example

The page opens on a 7-node graph: A–B 4, A–C 2, B–C 1, B–D 5, B–E 9, C–D 8, C–F 10, D–E 3, D–F 2, E–G 1, F–G 6. Starting from A:

• Tree {A}. Crossing edges: A–C 2, A–B 4. Take A–C 2.
• Tree {A, C}. Crossing: B–C 1, A–B 4, C–D 8, C–F 10. Take B–C 1.
• Tree {A, B, C}. A–B now lies inside the tree. Crossing: B–D 5, C–D 8, B–E 9, C–F 10. Take B–D 5.
• Tree {A, B, C, D}. Now D–F 2 and D–E 3 cross the cut: take D–F 2, then D–E 3, then E–G 1.

The result — A–C, B–C, B–D, D–F, D–E, E–G with total weight 14 — is the same tree Kruskal finds, built in a different order. Notice that Prim takes B–D 5 before the cheaper D–F 2 and E–G 1: it only ever sees edges that touch its own tree.

Prim vs Dijkstra: same skeleton, different key

Both algorithms pop the "closest" outside node from a priority queue and then update its neighbours. The only difference is what "closest" means. Dijkstra's key is the total distance from the source, dist[u] + w; Prim's key is the weight of the single edge that would attach the node to the tree, w.

That small change builds different trees. In a triangle with A–B 3, A–C 3 and B–C 2, Dijkstra from A keeps A–B and A–C (each node is 3 away from A, total weight 6), while Prim keeps B–C and one of the 3-edges (total weight 5). A shortest-path tree minimizes each node's distance to the root; a minimum spanning tree minimizes the sum of all edges.

Implementation choices

• Lazy heap of edges (the code below): push edges as nodes join and discard stale ones when popped. Each edge is pushed at most once, so it runs in O(E log E) = O(E log V).
• Eager version with an indexed heap: keep, for each outside node, only its cheapest connecting edge and lower it with decrease-key. Same bound, at most V heap entries.
• Array version: keep key[v] for every outside node and scan for the minimum each round — O(V²) with no heap at all, which is optimal for dense graphs such as all-pairs distances between points.
• The visualizer rescans every crossing edge each round so you can see them all highlighted; that is slower, but the chosen edges are identical.

Common mistakes and uses

• Using Dijkstra's key (dist[u] + w) and getting a shortest-path tree instead of an MST.
• Forgetting to discard stale edges whose far end is already in the tree, which creates cycles.
• Disconnected graphs: Prim only spans the start node's component. Restart from an unreached node to build a spanning forest.
• Directed graphs: MSTs are defined for undirected graphs only.

Prim shines on dense graphs: building a minimum network between points where every pair can be connected, clustering, and randomized Prim is a classic maze generator. Any start node gives a spanning tree of the same minimum total weight.

Time and space complexity

Prim's Algorithm in Python

import heapq


def prim(graph, s):
    """graph: {node: [(neighbour, weight)]} (undirected). Returns (mst, total weight)."""
    tree = {s}
    mst, total = [], 0
    C = [(w, s, v) for v, w in graph[s]]   # edges leaving the tree: a min-heap
    heapq.heapify(C)
    while len(tree) < len(graph):          # while nodes remain outside
        while C and C[0][2] in tree:       # drop edges that no longer leave the tree
            heapq.heappop(C)
        if not C:
            break                          # C is empty: disconnected
        w, a, b = heapq.heappop(C)         # cheapest edge in C
        tree.add(b)                        # add b and (a, b) to the tree
        mst.append((a, b, w))
        total += w
        for v, wv in graph[b]:
            if v not in tree:
                heapq.heappush(C, (wv, b, v))
    return mst, total

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Kruskal's Algorithm VisualizerKruskal's algorithm builds a minimum spanning tree by adding the cheapest edges that don't form a cycle, using union-find. Watch it step by step, with code.
• Dijkstra's Algorithm VisualizerDijkstra's algorithm finds the shortest paths from one node in a graph with non-negative weights. Watch every relaxation step by step, with heap-based code.
• Priority Queue VisualizerPriority queue visualizer: a binary heap always serves the top-priority item first. Watch insert, peek and extract in O(log n) and see how Dijkstra uses it.
• Graph Algorithm VisualizerInteractive graph algorithm visualizer: draw or generate a graph and step through BFS, DFS, Dijkstra, Bellman-Ford, Kruskal, Prim, topological sort and SCCs.