Prim's Algorithm

Prim’s algorithm builds a minimum spanning tree by growing one connected tree outward.

It repeatedly adds the cheapest edge from the current tree to a new vertex.

Core Idea

Start from any vertex. Keep a priority queue of edges that cross from the visited tree to unvisited vertices. Add the cheapest valid edge, then add the new vertex’s outgoing edges.

The algorithm is greedy, but the choice is constrained to edges that expand the current tree.

Function Contract

prim(graph, start) expects a weighted undirected adjacency list where graph[node] contains (neighbor, weight) pairs.

It returns (total, chosen) for the connected component reachable from start. In a disconnected graph, it does not produce a spanning tree for unreachable vertices.

Python Example

import heapq
 
def prim(graph, start):
    visited = {start}
    heap = [(weight, start, neighbor) for neighbor, weight in graph[start]]
    heapq.heapify(heap)
    total = 0
    chosen = []
 
    while heap:
        weight, source, node = heapq.heappop(heap)
        if node in visited:
            continue
 
        visited.add(node)
        total += weight
        chosen.append((source, node, weight))
 
        for neighbor, next_weight in graph[node]:
            if neighbor not in visited:
                heapq.heappush(heap, (next_weight, node, neighbor))
 
    return total, chosen

The graph is an adjacency list with weighted undirected edges.

Step-by-Step Idea

Prim’s algorithm keeps one growing connected region. At each step, it chooses the cheapest edge that leaves the region and reaches an unvisited vertex.

The visited set represents vertices already included in the tree. The heap stores candidate boundary edges.

Why It Works

At any moment, the visited and unvisited vertices form a cut. The cheapest edge crossing that cut is safe to add to some minimum spanning tree. Prim repeatedly applies this greedy choice until all vertices in the component are included.

Complexity

With an adjacency list and heap, Prim is commonly O(E log E) or O(E log V) depending on implementation details. It uses extra space for the heap and visited set.

Prim vs Kruskal

Prim grows from vertices. Kruskal scans sorted edges. Both solve MST problems, but their implementation shape is different.

Prim often feels natural when the graph is already in adjacency-list form. Kruskal often feels natural when the input is an edge list.

Common Confusions

Prim and Dijkstra both use a priority queue, but they optimize different things. Prim chooses the cheapest edge to expand the tree. Dijkstra chooses the smallest known distance from a start.

Prim assumes the graph can be expanded through available edges. A disconnected graph produces a spanning tree only for the reachable component.

Another common mistake is storing only the neighbor in the heap. The heap priority must be the edge weight, because Prim chooses the cheapest crossing edge.

When To Use It

Use Prim when the graph is naturally represented as adjacency lists and the solution should grow from a connected region.

Do not use Prim for directed shortest path or single-source distance problems.

The Main Point

Prim builds an MST by growing one connected region through the cheapest outgoing edge.