Prim's Algorithm

Prim's algorithm builds a minimum spanning tree (MST) of a connected, undirected, weighted graph by repeatedly adding the minimum-weight edge that connects the current tree to a new node. It is similar to [Dijkstra](/blog/algorithms/bfs-graph-traversal/dijkstra) but the key in the heap is the edge weight to reach a node, not the total path length.

When to Use

  • Find a minimum spanning tree (subset of edges that connects all vertices with minimum total weight).
  • Graph must be connected and undirected with edge weights.
  • Typical problems: connect all cities with minimum cable cost, minimum cost to supply water to all houses, etc.

Core Idea

  1. Start from any node; the tree is initially just that node.
  2. Maintain a min-heap of edges (weight, neighbor) that go from the current tree to a node not yet in the tree.
  3. Pop the smallest edge; if the neighbor is new, add the edge to the MST and add all edges from that neighbor to unvisited nodes into the heap.
  4. Repeat until the tree has V - 1 edges (or the heap is empty for a disconnected graph).

Java Implementation

Java
// adj.get(u) = list of {neighbor, weight}, undirected
int prim(List<List<int[]>> adj) {
    int n = adj.size();
    boolean[] inMst = new boolean[n];
    // min-heap: (weight, node)
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, 0}); // start from node 0 with cost 0

    int totalCost = 0;
    int edgesAdded = 0;

    while (!pq.isEmpty() && edgesAdded < n) {
        int[] cur = pq.poll();
        int w = cur[0], u = cur[1];
        if (inMst[u]) continue;
        inMst[u] = true;
        totalCost += w;
        edgesAdded++;

        for (int[] e : adj.get(u)) {
            int v = e[0], weight = e[1];
            if (!inMst[v]) {
                pq.offer(new int[]{weight, v});
            }
        }
    }
    return edgesAdded == n ? totalCost : -1; // -1 if disconnected
}

Time Complexity

  • Time: O((V + E) log V) with a binary heap — each edge is pushed at most once, and we do O(V) polls.
  • Space: O(V) for inMst and the heap.

Prim vs Kruskal

  • [Prim's Algorithm](/blog/algorithms/minimum-spanning-tree/prim) grows one tree from a start node; good when the graph is dense or you already have an adjacency structure.
  • [Kruskal's Algorithm](/blog/algorithms/minimum-spanning-tree/kruskal) sorts all edges and adds them in order (skipping cycles with [Union Find](/blog/algorithms/union-find/union-find-basics)); often simpler to code and good for sparse graphs.

Both produce an MST; the total weight is the same. Choose by implementation convenience or graph density.

Summary

Prim builds an MST by always adding the minimum-weight edge from the current tree to a new node. Use a min-heap of (weight, node) and a visited set. Stops when you have V - 1 edges (or when the heap is empty in a disconnected graph).