Prim's Algorithm Calculator

Pseudocode

Prim grows one tree outward from an arbitrary start. At every step it takes the cheapest edge with exactly one endpoint already in the tree.

Prim(graph, start):
    inTree = {start}
    pq = priority queue of edges leaving start
    mst = []

    while inTree does not contain all vertices:
        (u, v, w) = pq.extractMin()
        if v in inTree: continue      // stale, both ends inside

        mst.append((u, v, w))
        inTree.add(v)
        for each edge (v, x, w2):
            if x not in inTree: pq.insert((v, x, w2))

Correctness rests on the cut property: for any split of the vertices into two sides, the cheapest edge crossing that split belongs to some minimum spanning tree. Prim applies it with the split being "already in the tree" against "not yet", which is why taking the cheapest crossing edge is always safe and no backtracking is ever needed.

Worked example, step by step

Grow a minimum spanning tree from A on a small weighted graph where the greedy choice deliberately rejects a cheaper-looking direct edge.

Example graph: Undirected edges A-B (2), A-C (3), B-C (1), C-D (4) and B-D (7).

1. Start at A. The tree holds only A. The edges leaving it are A-B at 2 and A-C at 3.
2. Take A-B (2). A-B is the cheaper crossing edge, so B joins the tree. The frontier now holds A-C at 3, B-C at 1 and B-D at 7.
3. Take B-C (1). B-C at 1 is now the cheapest crossing edge, cheaper than the direct A-C at 3, so C joins through B. The direct A-C edge is never used. This is the step worth watching: a vertex adjacent to the start is not necessarily connected via the start.
4. A-C becomes internal. With both A and C in the tree, the A-C edge now has both endpoints inside and is discarded when it surfaces. That is the stale-entry check doing its job.
5. Take C-D (4). The remaining crossing edges are C-D at 4 and B-D at 7. C-D is cheaper, so D joins and the tree spans all four vertices.

The minimum spanning tree is A-B, B-C and C-D with total weight 2 + 1 + 4 = 7. Note that it has exactly three edges, one fewer than the four vertices, as every spanning tree must. Note also that the tree is a path here, which is a reminder that a minimum spanning tree is not a shortest-path tree: the tree distance from A to D is 7, while the graph shortest path A to C to D would be 3 + 4 = 7 and A to B to D is 9. The two problems optimise different things.

Complexity, and where it comes from

Time: O(E log V) · Space: O(V + E)

With a binary heap, each edge can be inserted once and extracted once at O(log E), and since E is at most V squared, log E is within a constant factor of log V, giving O(E log V). Each vertex is added to the tree exactly once. A Fibonacci heap with decrease-key instead of lazy insertion improves the bound to O(E + V log V), which is asymptotically better on dense graphs though rarely worth the constants. On a very dense graph, the simplest option wins: keep an array of the cheapest known edge to each outside vertex and scan it each round for O(V squared), which beats O(E log V) once E approaches V squared.

When to use Prim's MST Algorithm, and when not to

Prim and Kruskal both produce a minimum spanning tree. The right one depends on density and on how the edges arrive.

Common pitfalls

• Confusing a minimum spanning tree with a shortest-path tree. They are different objectives. An MST minimises total edge weight across the whole tree; a shortest-path tree minimises distance from one source to each vertex. In the example above the MST path from A to D costs 7 in tree edges, and in general an MST can make individual pairs much further apart than necessary.
• Skipping the stale-entry check. A lazy heap accumulates edges whose far endpoint later joins the tree by another route. Popping one of those and adding it creates a cycle and breaks the tree. Always test whether the target is already in the tree before accepting an edge.
• Running it on a disconnected graph. Prim grows one tree from one start and terminates when it can find no crossing edge. On a disconnected graph it returns a spanning tree of one component only. If you need a minimum spanning forest, restart from each unvisited vertex, or use Kruskal, which handles it naturally.
• Assuming the MST is unique. When several edges share a weight there can be many minimum spanning trees, all with the same total. The tree is unique only when all edge weights are distinct. Tests should compare total weight, not the edge set.
• Applying it to a directed graph. Spanning trees as Prim and Kruskal define them are undirected notions. The directed analogue is the minimum spanning arborescence, which needs the Chu-Liu/Edmonds algorithm; Prim gives wrong answers there.

Frequently asked questions

What is Prim's algorithm used for?

It finds a minimum spanning tree: the cheapest set of edges connecting every vertex of a weighted undirected graph. It is used to design low-cost networks such as power grids, fibre and telecom layouts, water pipelines and chip wiring, and it also underpins single-linkage clustering and some image segmentation methods.

What is the time complexity of Prim's algorithm?

O(E log V) with a binary heap, which is the usual implementation. A Fibonacci heap gives O(E + V log V), better asymptotically on dense graphs but with worse constants. On very dense graphs a simple O(V squared) array scan is actually faster because it avoids heap overhead entirely.

What is the difference between Prim's and Kruskal's algorithm?

Prim grows a single connected tree outward from a start vertex, always adding the cheapest edge that reaches a new vertex. Kruskal sorts all edges and adds any that does not close a cycle, growing a forest that merges into one tree. Prim suits dense graphs, Kruskal suits sparse ones or pre-sorted edges, and both give a minimum spanning tree.

Is a minimum spanning tree the same as a shortest path tree?

No. An MST minimises the total weight of all its edges; a shortest-path tree minimises the distance from one source to every vertex. They often differ, and an MST can leave two vertices far apart in tree distance even when a short direct edge exists, because using it would raise the total.

Does the starting vertex change the result?

It can change which edges are picked when weights are tied, but never the total weight. Prim produces a minimum spanning tree from any start. If all edge weights are distinct the tree is unique and the start vertex makes no difference at all.