Min Cost to Connect All Points

Min Cost to Connect All Points is a clean introduction to the Minimum Spanning Tree (MST): given a scatter of points, wire them all together for the least total cost. The standard tool is Prim's algorithm with a min-heap.

The slow way first

You could try every possible set of connecting edges and keep the cheapest valid one, but the number of edge subsets explodes — that is hopelessly slow. A smarter brute force sorts all pairs of points by cost and greedily joins them while avoiding cycles (that is Kruskal's algorithm), but it builds the full list of n² edges up front.

The question to ask: do I really need every edge at once? No. I can grow one connected tree outward, and at each moment only care about the cheapest edge that reaches a point I have not connected yet.

The idea: grow a tree, always take the cheapest reachable edge

This is Prim's algorithm. Keep a set of points already in_tree. Repeatedly pick the cheapest edge that links the tree to a point outside it, add that point, and add its cost to the total. A min-heap of (cost, point) makes "cheapest reachable edge" an O(log n) lookup.

The key insight: the heap may hold stale edges to points we already connected. We do not delete them — we just skip them when popped. That keeps each step simple.

Walk through it

Step through the animation. We seed the tree at A and push its edges. The heap always hands back the cheapest edge to an unconnected point: A-B (4), then B-D (3), then D-E (4), then finally B-C (9). The running total climbs to 20 once all five points are joined, and the highlighted edges are the MST.

Pseudocode

in_tree = empty set
heap = [(0, start_point)]          # (cost, point)
total = 0
while in_tree has fewer than n points:
    cost, u = pop smallest from heap
    if u already in in_tree:
        skip it (stale edge)
    add u to in_tree
    total += cost
    for every point v not in in_tree:
        push (manhattan_distance(u, v), v) onto heap
return total

The Python solution

def min_cost_connect_points(points):
    def dist(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])
    n = len(points)
    in_tree = set()
    heap = [(0, 0)]            # (cost, point index)
    total = 0
    while len(in_tree) < n:
        cost, u = heapq.heappop(heap)
        if u in in_tree:
            continue          # stale edge, skip
        in_tree.add(u)
        total += cost
        for v in range(n):
            if v not in in_tree:
                heapq.heappush(heap, (dist(points[u], points[v]), v))
    return total

• dist is the Manhattan distance — the cost to connect two points.
• heap holds (cost, point) pairs; heapq always pops the smallest cost first.
• We seed with (0, 0): reaching the start point costs nothing.
• Line 10 skips a popped edge if that point is already in the tree — that is how we ignore stale entries instead of deleting them.
• When we add a fresh point u, we push an edge from u to every point not yet connected, so the frontier stays complete.
• We stop the moment all n points are in_tree, and total is the MST cost.

Complexity

Because each newly added point pushes an edge to every other point, the heap can hold O(n²) entries, giving O(n² log n) time and O(n²) space. That is the standard Prim cost on a dense graph, and points are dense — every pair is connectable.

When this pattern shows up

Practice