Minimum Spanning Tree

Objectives and sequence#

• Distinguish minimum total connection cost from shortest paths out of one source.
• Build a deterministic Kruskal solution with disjoint-set union.
• Use cycle and cut intuition to justify accepting or rejecting an edge.
• State an explicit connected/disconnected result contract and compare Prim conceptually.

Recognition boundaries#

From baseline to method#

Simple baseline: Enumerate subsets of n-1 edges, keep only connected acyclic subsets, and choose the minimum weight. This is exponential and repeats connectivity work across subsets.

1. A spanning tree connects all n vertices with n-1 edges and no cycle. Its objective is total selected weight, unlike a shortest-path tree's per-source distances.
2. Normalize undirected endpoints and sort by (weight,u,v) so tied inputs produce deterministic output.
3. For each edge, DSU reports whether its endpoints are already connected. Rejecting a same-component edge preserves acyclicity; accepting a cross-component edge merges two trees.
4. Cut intuition: for any cut separating current components, a lightest crossing edge is safe for some MST. Kruskal repeatedly chooses such safe edges in global weight order.
5. Stop after n-1 accepted edges. If fewer can be accepted after all edges, return a minimum spanning forest with connected=false and no MST total.
6. Prim grows one connected tree with the cheapest crossing edge from its frontier, commonly using a heap; Kruskal grows and merges a forest. Both optimize the MST objective under the same undirected weighted-graph contract.

Worked example#

Run deterministic Kruskal on vertices 0..4. Return accepted edges, total weight when connected, and the connectivity flag.

Input

edges = [(0,1,-2), (0,1,-2), (1,2,1), (0,2,1), (2,3,2), (1,3,2), (3,4,3), (2,4,4)]

Contract

The graph is undirected; vertices are exactly 0..n-1; parallel, duplicate, tied, and negative-weight edges are allowed; weights and their accepted sum fit the chosen integer type.

Expected

connected=true, totalWeight=4, edges=[(0,1,-2),(0,2,1),(1,3,2),(3,4,3)]

Trace summary: Sort by weight then normalized endpoints. Accept an edge exactly when its endpoints are in different DSU components, until four edges connect the five vertices.

Pseudocode and tested references#

The pseudocode leaves DSU mechanics and result syntax abstract. The tested references include path compression, union by size, deterministic endpoint normalization, and an explicit null/None MST total for disconnected graphs while preserving the selected forest edges.

kruskal(vertexCount, edges):
  normalize each undirected edge so u <= v
  sort edges by (weight, u, v)
  dsu = one component per vertex
  accepted = empty list; total = 0
  for edge in sorted edges:
    if dsu.union(edge.u, edge.v):
      append edge to accepted; total += edge.weight
      if accepted.length == vertexCount - 1: break
  connected = (vertexCount == 0) or (accepted.length == vertexCount - 1)
  return {connected, totalWeight: connected ? total : none, forestEdges: accepted}

def kruskal(vertex_count, edges):
    parent = list(range(vertex_count))
    size = [1] * vertex_count

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

    def union(a, b):
        root_a, root_b = find(a), find(b)
        if root_a == root_b:
            return False
        if size[root_a] < size[root_b]:
            root_a, root_b = root_b, root_a
        parent[root_b] = root_a
        size[root_a] += size[root_b]
        return True

    normalized = [(weight, min(u, v), max(u, v)) for u, v, weight in edges]
    accepted = []
    total = 0
    for weight, u, v in sorted(normalized):
        if union(u, v):
            accepted.append((u, v, weight))
            total += weight
            if len(accepted) == max(0, vertex_count - 1):
                break
    connected = vertex_count == 0 or len(accepted) == vertex_count - 1
    return {"connected": connected, "total_weight": total if connected else None, "forest_edges": accepted}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public final class MinimumSpanningTreeReference {
    public record Edge(int u, int v, long weight) {}
    public record MstResult(boolean connected, Long totalWeight, List<Edge> forestEdges) {}

    private static final class Dsu {
        private final int[] parent;
        private final int[] size;
        Dsu(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
        }
        int find(int node) {
            while (node != parent[node]) {
                parent[node] = parent[parent[node]];
                node = parent[node];
            }
            return node;
        }
        boolean union(int a, int b) {
            int rootA = find(a), rootB = find(b);
            if (rootA == rootB) return false;
            if (size[rootA] < size[rootB]) { int swap = rootA; rootA = rootB; rootB = swap; }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
            return true;
        }
    }

    public static MstResult kruskal(int vertexCount, List<Edge> edges) {
        List<Edge> sorted = edges.stream()
            .map(edge -> new Edge(Math.min(edge.u(), edge.v()), Math.max(edge.u(), edge.v()), edge.weight()))
            .sorted(Comparator.comparingLong(Edge::weight).thenComparingInt(Edge::u).thenComparingInt(Edge::v))
            .toList();
        Dsu dsu = new Dsu(vertexCount);
        List<Edge> accepted = new ArrayList<>();
        long total = 0;
        for (Edge edge : sorted) {
            if (dsu.union(edge.u(), edge.v())) {
                accepted.add(edge);
                total += edge.weight();
                if (accepted.size() == Math.max(0, vertexCount - 1)) break;
            }
        }
        boolean connected = vertexCount == 0 || accepted.size() == vertexCount - 1;
        return new MstResult(connected, connected ? total : null, List.copyOf(accepted));
    }
}

Time

O(E log E) for deterministic edge sorting, plus O(E α(V)) for DSU operations.

Space

O(V + E) for DSU state and the normalized sorted edge list; accepted output contains at most V-1 edges.

Assumptions

The graph is static, undirected, and vertex IDs are 0..V-1; comparison keys and the accepted weight sum fit their types; α is the inverse Ackermann function under path compression and union by size.

Failure modes and edges#

Edge cases

• Zero vertices is connected by this lesson's explicit empty-graph convention and has total weight 0.
• One isolated vertex is connected with no accepted edges and total weight 0.
• A disconnected graph returns connected=false, totalWeight=null, and the minimum forest edges selected by the same pass.
• Duplicate and parallel edges are legal; DSU rejects those whose endpoints are already connected.
• Negative weights are legal and should be considered before nonnegative edges.
• Tied weights can yield multiple valid MSTs; sorting normalized endpoints makes this reference output deterministic.
• Self-loops are rejected because their endpoints already share a component.

Wrong approaches

Three-stage hint ladder#

Narrated reasoning

The objective is minimum total cost to connect every vertex, so I am solving an MST rather than source shortest paths. Kruskal fits an edge list: sort once and use DSU to maintain the forest components. A same-component edge would close a cycle, so I reject it even when it is tied or negative. I normalize endpoints and add tie keys only for deterministic output; the cut argument supplies optimality. At the end I require V-1 accepted edges, otherwise I return an honestly labeled minimum spanning forest with no MST total.

Reasoning checkpoints#

Guided exercises

• Run Kruskal on four vertices with edges (0,1,1) and (2,3,1). State the exact result contract.
  Checkpoint: connected=false, totalWeight=null, and both edges appear in the minimum spanning forest.

Practice and transfer#

Unseen variant: Some vertices are isolated and the caller wants one minimum tree per connected component. Return component-grouped forest edges and weights rather than a single nullable MST total.

Checkpoint: Run Kruskal unchanged, then group accepted edges and isolated vertices by final DSU representative; label the output a minimum spanning forest, not an MST.

Practice handoffs

• Practice minimum connection costChoose and justify Prim or Kruskal for a complete weighted graph.
• Review union-findRehearse representative and merge invariants before implementing Kruskal.

Follow-up constraints

• Implement Prim with a heap and compare its complexity on sparse versus implicit dense graphs.
• Prove the next accepted Kruskal edge is safe using a cut between its two current components.
• How would you validate endpoint IDs before DSU access without confusing input validation with the algorithm invariant?

Sources and review#

This original Engineering Foundry lesson received Codex self-review on 2026-09-05; independent human editorial review is not claimed.

• Minimum spanning tree - Kruskal with Disjoint Set Union (opens in a new tab) - Sorted-edge Kruskal, DSU cycle checks, and O(E log E) complexity.
• MIT 6.006 Introduction to Algorithms lecture notes (opens in a new tab) - Academic cross-check for graph, heap, and shortest-path distinctions; not an interview-frequency claim.