Prim

Kruskal’s method grows many small trees and joins them. Prim’s method grows one tree from a starting vertex, adding the cheapest edge that leaves it at every step. It looks like Dijkstra’s method, and the code is almost the same.

Grow one tree

1. Start with a tree of one vertex, any vertex.
2. Look at every edge with one end in the tree and the other end outside it. Take the cheapest, and add it and its outside vertex.
3. Repeat until every vertex is in the tree.

Vojtěch Jarník found it in 1930; Robert Prim (1957) and Edsger Dijkstra (1959) found it again. Lesson 4 proves it: the edges leaving the tree are exactly the edges crossing the cut between the tree and the rest, and the cheapest edge across any cut is safe to take.

With heapq

The heap holds candidate vertices with the cost of the cheapest known edge from the tree to them. As in Dijkstra’s method (PATH-3), an improvement pushes a new entry, and old entries are skipped when they come out (lazy removal, HEAP-4). Step through the figure.

import heapq

def prim(adj, s=0):              # adj[u]: list of (v, w), both ways
    n = len(adj)
    in_tree = [False] * n
    total, count = 0, 0
    heap = [(0, s)]               # (cost of the edge into v, v)
    while heap and count < n:
        w, u = heapq.heappop(heap)
        if in_tree[u]:
            continue              # an old entry
        in_tree[u] = True
        total += w
        count += 1
        for v, c in adj[u]:
            if not in_tree[v]:
                heapq.heappush(heap, (c, v))
    return total if count == n else None

The only change from Dijkstra is the number pushed: Dijkstra pushes d + w, the length of a whole route from the start; Prim pushes c, the cost of one edge. Each edge can push one entry, so the cost is O(E log V), the same as Kruskal. To get the edges and not only the total, push (c, v, u) and record u as v’s parent when v joins the tree.

Dense graphs: no heap

When almost every pair of vertices is joined (E close to V², which is V times V), the heap holds up to V² entries and the edges alone take V² memory. A plain list does better. Keep best[v], the cheapest edge from the tree to v. Each step scans all outside vertices for the smallest best (O(V)), adds that vertex, and lowers best for the others using edges to the new vertex (O(V)). In all O(V²) time and O(V) extra memory, and the edges never need to be stored if their costs can be worked out, such as distances between points.

For V points on a plane, every pair is an edge: about 2 million for 2,000 points. Listing and sorting them for Kruskal costs O(V² log V) time and lots of memory; the list version of Prim costs O(V²) and almost no memory. That is SPAN-P3.

Prim, Kruskal, and Dijkstra

A cheapest spanning tree is not a tree of shortest routes. In a triangle with edges A–B 2, B–C 2 and A–C 3, the cheapest tree uses A–B and B–C (cost 4), so the route from A to C in the tree takes 4, while the direct edge takes 3. Dijkstra from A keeps A–C. Each tree is the best at its own question.

Now try SPAN-P3, Connect the points.