Prim's Algorithm

Prim's algorithm grows a minimum spanning tree from a start vertex, always adding the cheapest edge that reaches a new vertex.

Grow one tree outward

Prim's algorithm builds a minimum spanning tree by starting from an arbitrary vertex and repeatedly adding the cheapest edge that connects the growing tree to a vertex not yet in it. It maintains a single connected tree throughout, expanding it one vertex at a time until all vertices are included.

Why it works

At each step the set of vertices in the tree and the set outside it form a cut. By the cut property, the lightest edge crossing that cut is safe to add to some minimum spanning tree, and that is exactly the edge Prim's picks. Because every choice is provably safe, the final tree is optimal.

• Time: O(E log V) with a binary-heap priority queue
• Time: O(V^2) with a simple array, better for dense graphs
• Maintains one connected tree at all times
• A greedy algorithm justified by the cut property

import heapq
def prim(graph, start):
    seen = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    total = 0
    while pq:
        w, _, v = heapq.heappop(pq)
        if v in seen: continue
        seen.add(v); total += w
        for nb, nw in graph[v]:
            if nb not in seen:
                heapq.heappush(pq, (nw, v, nb))
    return total

The difference from Dijkstra

Prim's and Dijkstra's share the priority-queue skeleton but key on different quantities. Dijkstra's priority is the total distance from the source, accumulated along the path; Prim's priority is just the weight of the single edge connecting a vertex to the tree. That one change turns a shortest-path algorithm into a minimum-spanning-tree algorithm.

Prim's versus Kruskal's

Prim's algorithm resembles Dijkstra's in structure, using a priority queue keyed by edge weight, and it favours dense graphs where its O(V^2) array form shines. Kruskal's algorithm, which sorts all edges globally, tends to suit sparse graphs. Both produce a valid minimum spanning tree, and on a graph with distinct weights they produce the same one.