AlgoInsight

Q&A

What is Prim's algorithm?

By AlgoInsight Team2026-06-07algorithmsdata-structures

Overview

A spanning tree connects all V vertices of a graph with exactly V-1 edges and no cycles; the minimum spanning tree minimizes total edge weight. Prim's builds the MST by growing a single tree outward, always choosing the lowest-weight edge that reaches a not-yet-included vertex. It's a classic greedy algorithm and one of the two standard MST methods (the other being Kruskal's).

graph TD
    A[Start at any vertex; tree = that vertex] --> B[Look at all edges crossing tree → outside]
    B --> C[Pick the minimum-weight crossing edge]
    C --> D[Add its new vertex to the tree]
    D --> E{All vertices in tree?}
    E -->|no| B
    E -->|yes| F[MST complete: V-1 edges, min total weight]
    style C fill:#1e1b4b,color:#fff

How It Works

  1. Start with any single vertex as the initial tree.
  2. Consider all edges that cross from the tree to vertices outside it.
  3. Add the minimum-weight such edge (and its new vertex) to the tree.
  4. Repeat until every vertex is included (V-1 edges added).

The greedy choice - always take the cheapest edge expanding the tree - provably yields a globally minimum spanning tree (the "cut property").

Implementation (priority queue, O(E log V))

import heapq

def prim(graph, start):
    # graph: dict vertex -> list of (neighbor, weight)
    visited = set()
    mst_edges = []
    total = 0
    pq = [(0, start, None)]            # (weight, vertex, from)

    while pq and len(visited) < len(graph):
        weight, u, frm = heapq.heappop(pq)
        if u in visited:
            continue                    # skip vertices already in the tree
        visited.add(u)
        if frm is not None:
            mst_edges.append((frm, u, weight))
            total += weight
        for v, w in graph[u]:
            if v not in visited:
                heapq.heappush(pq, (w, v, u))   # candidate crossing edges

    return mst_edges, total

graph = {
    "A": [("B", 1), ("C", 4)],
    "B": [("A", 1), ("C", 2), ("D", 5)],
    "C": [("A", 4), ("B", 2), ("D", 1)],
    "D": [("B", 5), ("C", 1)],
}
print(prim(graph, "A"))
# edges A-B(1), B-C(2), C-D(1); total = 4

The priority queue always yields the cheapest edge crossing out of the current tree; visited-checking prevents cycles.

Complexity

Implementation Time
Adjacency matrix + linear min scan O(V²)
Adjacency list + binary heap O(E log V)
Adjacency list + Fibonacci heap O(E + V log V)

For dense graphs the O(V²) version can be competitive; for sparse graphs the heap-based O(E log V) is preferred.

Prim's vs Kruskal's

Both find an MST greedily but differently:

Prim's Kruskal's
Grows One tree outward from a start vertex Merges a forest of trees
Picks Cheapest edge leaving the current tree Cheapest edge overall that doesn't form a cycle
Data structure Priority queue Sorted edges + Union-Find
Better for Dense graphs Sparse graphs

Both are correct; the choice is often about graph density and which structure is handier.

Applications

Network design (minimum cabling/piping to connect all nodes), clustering, approximation algorithms (e.g. for TSP), and any "connect everything as cheaply as possible" problem.

Why This Matters in Interviews

Graph/algorithm interviews use Prim's to test greedy reasoning and MST knowledge. Key points: it builds the MST by repeatedly adding the minimum-weight edge crossing from the tree to a new vertex, using a priority queue for O(E log V); the result has V-1 edges and minimum total weight; and the greedy choice is justified by the cut property. Contrasting Prim's (grows one tree, PQ) with Kruskal's (merges a forest, Union-Find) - and noting density preferences - demonstrates breadth.

Common Pitfalls

References

More answers