Minimum Spanning Trees — Connecting Everything at Minimum Cost

A spanning tree of a connected undirected graph is a subgraph that includes all vertices and is a tree (connected, acyclic). A minimum spanning tree (MST) is the spanning tree with the smallest total edge weight. The key insight: a spanning tree of V vertices always has exactly V-1 edges. The MST problem asks which V-1 edges to keep.

The classic motivation: you have a set of cities. You want to connect all of them with roads using the minimum total road construction cost. You don’t need every possible road — just enough to keep every city reachable. That’s an MST.

Why Greedy Works for MST — The Cut Property

Both MST algorithms are greedy. This works because of a fundamental property called the cut property:

Given any partition of the vertices into two non-empty sets S and V\S (a “cut”), the minimum weight edge crossing the cut is in every MST.

Proof intuition: suppose edge e (the minimum crossing edge) is NOT in some MST T. Then T must use some other crossing edge e’ (to keep the graph connected across the cut). If we swap e’ for e, we get a spanning tree with smaller total weight — contradicting T being an MST. Therefore e must be in T.

The two MST algorithms differ in how they choose which cut to inspect at each step. Kruskal’s processes edges globally by weight. Prim’s grows a single component outward.

Kruskal’s Algorithm

Strategy: sort all edges by weight. Add edges in order of increasing weight, skipping any edge that would create a cycle (i.e., whose endpoints are already connected). Stop when V-1 edges have been added.

The cycle detection step is what Union-Find was built for.

int kruskalMST(int V, int[][] edges) {
    // edges[i] = {u, v, weight}
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));  // sort by weight

    UnionFind uf = new UnionFind(V);
    int totalWeight = 0;
    int edgesAdded = 0;

    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];

        if (uf.union(u, v)) {       // returns false if u, v already connected
            totalWeight += w;
            edgesAdded++;
            if (edgesAdded == V - 1) break;  // MST complete: exactly V-1 edges
        }
    }

    // If edgesAdded < V-1: graph was disconnected, no spanning tree exists
    return totalWeight;
}

Time: O(E log E) for sorting + O(E × α(V)) for Union-Find operations ≈ O(E log E). Space: O(V) for Union-Find.

Kruskal’s is edge-centric: it works naturally from an edge list. The sort dominates the runtime.

Prim’s Algorithm

Strategy: grow an MST from a single starting vertex. Maintain a set of vertices already in the MST. At each step, add the minimum-weight edge that connects a vertex in the MST to a vertex outside it. Repeat until all vertices are included.

This is conceptually similar to Dijkstra: use a min-heap tracking the minimum cost to add each vertex to the growing MST.

int primMST(int V, List<int[]>[] adj) {
    // adj[u] contains int[] {v, weight} for each edge u-v
    boolean[] inMST = new boolean[V];
    int[] minCost = new int[V];     // min edge cost to add vertex i to MST
    Arrays.fill(minCost, Integer.MAX_VALUE);
    minCost[0] = 0;                 // start from vertex 0

    // Min-heap: {cost, vertex}
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, 0});

    int totalWeight = 0;

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int cost = curr[0], node = curr[1];

        if (inMST[node]) continue;    // stale entry: node already in MST
        inMST[node] = true;
        totalWeight += cost;

        for (int[] edge : adj[node]) {
            int neighbor = edge[0], weight = edge[1];
            if (!inMST[neighbor] && weight < minCost[neighbor]) {
                minCost[neighbor] = weight;
                pq.offer(new int[]{weight, neighbor});
            }
        }\n    }

    return totalWeight;
}

Time: O((V + E) log V). Each vertex is added to the PQ at most once per incoming edge; PQ operations are O(log V). Space: O(V + E).

Prim’s is vertex-centric: it grows a single connected component outward. Better than Kruskal’s on dense graphs (E ≈ V²) where the sort cost of Kruskal dominates.

Kruskal’s vs Prim’s

Kruskal’s

Prim’s

Strategy

Edge-sorted, add globally

Grow single component outward

Data structure

Union-Find

Priority queue

Time

O(E log E)

O((V+E) log V)

Better for

Sparse graphs (E ≈ V)

Dense graphs (E ≈ V²)

Connectivity required

No (handles disconnected)

Must start from a connected component

Implementation

Edge list + sort

Adjacency list + heap

For LeetCode, either works. Kruskal’s with Union-Find is slightly easier to implement correctly because the cycle detection is handled by DSU. Prim’s is worth knowing because it parallels Dijkstra structurally.

MST Variant: Minimum Cost to Connect All Points (LC 1584)

Points on a 2D plane, no explicit edges. You can connect any two points at cost = Manhattan distance. Find the MST of the complete graph.

Kruskal’s approach: generate all C(n,2) = O(n²) edges, sort them, run Kruskal’s. For n ≤ 1000, this is 500,000 edges — manageable.

Prim’s approach: avoid generating all edges. For each vertex not yet in the MST, track the minimum Manhattan distance to any vertex currently in the MST. Update after each MST expansion. This avoids materializing all edges.

int minCostConnectPoints(int[][] points) {
    int n = points.length;
    int[] minDist = new int[n];   // min distance to MST for each point
    Arrays.fill(minDist, Integer.MAX_VALUE);
    minDist[0] = 0;

    boolean[] inMST = new boolean[n];
    int totalCost = 0;

    for (int i = 0; i < n; i++) {
        // Find the non-MST point with minimum distance (linear scan = Prim's without heap)
        int next = -1;
        for (int j = 0; j < n; j++) {
            if (!inMST[j] && (next == -1 || minDist[j] < minDist[next])) {
                next = j;
            }
        }

        inMST[next] = true;
        totalCost += minDist[next];

        // Update distances to all non-MST points
        for (int j = 0; j < n; j++) {
            if (!inMST[j]) {
                int dist = Math.abs(points[next][0] - points[j][0])
                         + Math.abs(points[next][1] - points[j][1]);
                minDist[j] = Math.min(minDist[j], dist);
            }
        }
    }

    return totalCost;
}

This is Prim’s without a heap (O(V²)), which is optimal for the complete graph where E = V² anyway.

Critical Connections and Bridges (LC 1192)

Not strictly MST, but a related concept worth placing here: a bridge is an edge whose removal disconnects the graph. Finding all bridges uses DFS with discovery/low-time tracking.

// Low[u] = minimum discovery time reachable from the subtree rooted at u
// If low[v] > disc[u], then edge u-v is a bridge (v can't reach back above u)

void dfs(int u, int parent, int[] disc, int[] low, boolean[] visited, List<List<Integer>> adj, List<List<Integer>> result) {
    visited[u] = true;
    disc[u] = low[u] = timer++;

    for (int v : adj.get(u)) {
        if (v == parent) continue;
        if (!visited[v]) {
            dfs(v, u, disc, low, visited, adj, result);
            low[u] = Math.min(low[u], low[v]);
            if (low[v] > disc[u]) {    // v can't reach back to u or above: bridge
                result.add(Arrays.asList(u, v));
            }
        } else {
            low[u] = Math.min(low[u], disc[v]);
        }
    }
}

The low[] value propagates upward via DFS, encoding the earliest-discovered node reachable from each subtree.

Applications

  • Network design: minimum cost infrastructure (cable, roads, pipelines) connecting all nodes

  • Clustering: Kruskal’s MST + remove k-1 heaviest edges → k clusters (used in k-means seeding)

  • Approximation algorithms: the 2-approximation for TSP uses an MST as its backbone

  • Image segmentation: group pixels by similarity; minimum spanning tree of the pixel graph, then cut

Practice Problems

#

Problem

Difficulty

Focus

1

LC 1584 — Min Cost to Connect All Points

Medium

Prim’s or Kruskal’s on complete graph

2

LC 1135 — Connecting Cities With Minimum Cost

Medium

Direct MST application

3

LC 1192 — Critical Connections (Bridges)

Hard

DFS with low-time tracking

4

LC 1489 — Find Critical and Pseudo-Critical Edges

Hard

MST + edge classification

Problem 1 is the essential MST problem on LeetCode. Solve it with both Kruskal’s and Prim’s. Problem 3 introduces bridge-finding — a DFS technique that extends the graph toolkit beyond MST proper.