Minimum spanning trees

Problem

You must link every point, city or server so that everything is reachable from everything else, paying for each link, and you want the total cost minimum. The answer has no cycles (a cycle's costliest edge would be wasted) and exactly n - 1 edges. Trying all subsets of edges is exponential; a greedy order is enough.

Intuition

Pretend you are laying cable. Start with the cheapest link you could ever lay, then the next cheapest, skipping any that would join two places that are already connected. That is Kruskal's. Or stand at one place and keep extending to the cheapest neighbor of everything you have wired up so far. That is Prim's. Both feel too naive to be optimal, and both are, for the same reason.

The cut property. Split the nodes into any two groups. The cheapest edge crossing between them belongs to some minimum spanning tree. Why: take any tree that lacks that edge; adding it creates a cycle, and that cycle must cross the split at a second edge that costs at least as much. Swapping that edge out for the cheapest one cannot make the tree more expensive. Kruskal's picks an edge that is the cheapest crossing out of one component, and Prim's picks the cheapest crossing out of the grown tree, so each pick is safe.

Thick edges form the tree of total weight 14. The diagram scrolls sideways on a narrow screen.

Mechanics

Kruskal's algorithm

Sort all edges by weight. Walk them in order; for each, ask union-find whether its endpoints are already in the same component. If not, take the edge and union them; if so, skip it, since it would close a cycle. Stop after n - 1 edges. If fewer than n - 1 were taken, the graph was not connected.

Prim's algorithm

Start at any node and push its edges onto a min-heap. Repeatedly pop the cheapest edge; if its far end is already in the tree, skip it, otherwise add the node and push that node's edges. It is Dijkstra's loop with the key changed from "distance from the start" to "weight of the single connecting edge".

Invariants

After every step the chosen edges are a subset of some minimum spanning tree (by the cut property), and they never form a cycle. When n - 1 edges are taken in a connected graph, the set is a spanning tree and so a minimum one. Ties can make the final tree differ between the two algorithms, but never the total.

Choosing between them

With an explicit edge list, Kruskal's is the shortest to write. With a dense or implicit graph, such as every pair of points, Prim's array version runs in O(n²) without ever listing the edges.

Blue bars are taken edges. An edge is skipped exactly when its ends were already connected by cheaper edges.

Worked example

Kruskal's on the graph above sorts the edges and decides each in turn: 1-2 (1) taken; 1-3 (2) taken; 3-4 (2) taken; 0-2 (3) taken; 0-1 (4) skipped; 2-3 (4) skipped; 4-5 (6) taken; 3-5 (6) skipped; 2-4 (7) skipped. The tree has 5 edges and total weight 14.

Prim's from node 0 adds 0-2 (3), 2-1 (1), 1-3 (2), 3-4 (2), 3-5 (6), also totalling 14. Its last edge is 3-5, where Kruskal's took 4-5: nodes 3 and 4 both reach node 5 at cost 6, a tie, so the trees differ but the totals do not.

Connecting points. For the points [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]] with Manhattan distance between points as the cost, the cheapest way to join them all costs 20.

Critical and pseudo-critical edges. Number the edges above from 0 in the order listed. Removing any of edges 1, 2, 3, 5 raises the minimum total (or disconnects the graph), so they are in every minimum tree. Edges 7 and 8 can appear in some minimum trees but not all, because the tie at cost 6 lets either reach node 5.

Implementation

def kruskal(n, edges):
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = used = 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            total += w
            used += 1
            if used == n - 1:
                break
    return total if used == n - 1 else -1


import heapq

def prim(n, graph):
    # graph[u] is a list of (weight, v)
    seen = {0}
    heap = list(graph[0])
    heapq.heapify(heap)
    total = 0
    while heap and len(seen) < n:
        w, v = heapq.heappop(heap)
        if v in seen:
            continue
        seen.add(v)
        total += w
        for item in graph[v]:
            if item[1] not in seen:
                heapq.heappush(heap, item)
    return total if len(seen) == n else -1

Variations and edge cases

def min_cost_connect_points(points):
    n = len(points)
    best = [float("inf")] * n
    best[0] = 0
    used = [False] * n
    total = 0
    for _ in range(n):
        u = min((i for i in range(n) if not used[i]), key=best.__getitem__)
        used[u] = True
        total += best[u]
        for v in range(n):
            if not used[v]:
                d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                best[v] = min(best[v], d)
    return total

• Disconnected graph. There is no spanning tree, only a spanning forest. Check the edge count and return the sentinel the problem asks for.
• Maximum spanning tree. Sort descending (Kruskal) or negate the weights.
• Ties. Several minimum trees can exist; the total is unique. Only the "critical edge" questions care which one you got.
• Skip or force an edge. To classify an edge, rerun Kruskal with it removed (a higher total or a disconnection means it is critical) or with it forced in first (the same total means it can appear).
• Dense graphs. Building all n² point pairs and sorting is O(n² log n); the array form of Prim's above is O(n²).
• Edge cases: one node (cost 0), duplicate points (zero-cost edges), parallel edges (the cheapest wins), and self-loops (always skipped).

Complexity and tradeoffs

• Kruskal's: O(E log E) for the sort, plus near-linear union-find work.
• Prim's with a heap: O(E log V). With an array scan on a dense graph: O(V²).
• Space: O(V + E) for the edges and heap or union-find.
• Baseline. Enumerating spanning trees is exponential in general.
• When it fails. The tree minimizes total weight, not distances between pairs, so use Dijkstra for routes. For directed graphs (minimum arborescence) you need Chu-Liu/Edmonds, which is rare in interviews.

Problems

Min Cost to Connect All Points is the standard run: no edge list is given, so Prim's on the implicit complete graph (or Kruskal's over generated pairs) fits. Find Critical and Pseudo-Critical Edges asks which edges every, or some, minimum trees contain, answered by the skip and force reruns of Kruskal's.

Medium

• 1584. Min Cost to Connect All Points NeetCode 150 NeetCode 250
  With every pair of points connected, Prim's algorithm with an array of best distances runs in O(n^2) without building edges.

Hard

• 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree NeetCode 250
  An edge is critical if removing it raises the MST weight, and pseudo-critical if forcing it in keeps the weight unchanged.

Connections

Kruskal's uses union-find as its cycle test, and Prim's reuses the heap loop of Dijkstra with a different key. A minimum spanning tree also gives the smallest possible largest edge on a path between two nodes, which links it to the bottleneck problems solved by sorting edges and joining components.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 21 (minimum spanning trees, the cut property, Kruskal and Prim).
• Kruskal, "On the shortest spanning subtree of a graph and the traveling salesman problem", Proceedings of the AMS 7(1), 1956.
• Prim, "Shortest connection networks and some generalizations", Bell System Technical Journal 36(6), 1957.
• Sedgewick and Wayne, Algorithms, section 4.3 (minimum spanning trees).
• Skiena, The Algorithm Design Manual: the minimum spanning tree section of the weighted graph chapter, and the catalog entry on minimum spanning trees.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.