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.

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.

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.

When To Use It

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