Connecting everything cheaply

Not a shortest path. The cheapest set of edges that leaves nothing isolated.

Why it works

Grow one component, always taking the cheapest edge leaving it

Start from any node. Repeatedly take the cheapest edge connecting the grown set to something outside it, and absorb that node. Stop when everything is inside.

A heap holds the candidate edges leaving the current set, which is exactly the structure that hands back the smallest. The shape of the loop is nearly identical to the shortest-path one, and the difference is one expression: push the edge weight rather than the accumulated total.

Here is the very first step, with one node inside the set and every edge out of it offered to the heap.

1import heapq2 3points = [(0, 0), (2, 2), (3, 10), (5, 2)]4 5def distance(p, q):6    return abs(p[0] - q[0]) + abs(p[1] - q[1])7 8inside = {0}9heap = []10for other in range(len(points)):11    if other not in inside:12        heapq.heappush(heap, (distance(points[0], points[other]), other))13 14print("edges leaving the set:", sorted(heap))15weight, node = heapq.heappop(heap)16print("cheapest crossing:", weight, "to node", node)

Absorb node 1, then offer its edges too. Nodes already inside are skipped when they surface.

Quick check· 5 min

What changes between the two algorithms?

You have working code for weighted shortest paths from a start node. What single change turns it into a minimum spanning tree algorithm?

Push neighbors with the edge weight alone rather than with the accumulated cost from the startTake the largest candidate from the heap instead of the smallestMark nodes as finalized when they are pushed rather than when they are poppedSort the adjacency lists before starting

Problem· 30 min

Min Cost To Connect All Points

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1import heapq2 3points = [(0, 0), (2, 2), (3, 10), (5, 2)]4 5def distance(p, q):6 return abs(p[0] - q[0]) + abs(p[1] - q[1])7 8inside = {0}9heap = []10for other in range(len(points)):11 if other not in inside:12 heapq.heappush(heap, (distance(points[0], points[other]), other))13 14print("edges leaving the set:", sorted(heap))15weight, node = heapq.heappop(heap)16print("cheapest crossing:", weight, "to node", node)