DSA Graphs

Minimum Spanning Tree

You need fiber to every house. Extra loops burn budget and add no connectivity. Dual conflict: the mesh is correct for redundancy; the finance review is not. You want a minimum-weight .

Greedy MST algorithms are justified by the and , not by vibes. Prim grows a tree; Kruskal merges forests.

Decision journey

Undirected + connected?

Directed “MST” is a different problem.

Safe to take a light crossing edge.

Safe to reject a cycle-closing heavy edge.

Prim vs Kruskal

Dense adjacency vs sorted edge list.

What actually happens

Naive idea: sort edges and keep adding forever, or take a shortest-path tree from one root. Breaks: extra edges create cycles; a shortest-path tree minimizes path costs from a root, not total spanning weight.

Better idea: only add a that is safe by the cut property, or skip edges unsafe by the cycle property, until you have V−1 edges (or a forest if disconnected).

The improved design still fails on directed graphs, on “must be unique” when weights tie, and if you return a tree when the input was disconnected without stating the forest contract.

Invariant

Every edge accepted so far belongs to some MST of the original graph (or some MSF if disconnected). The growing structure stays acyclic; when connectedness is required, it ends with exactly V−1 edges.

How to choose an MST algorithm

1. Sparse edge list? Kruskal + Union-Find is natural.

2. Dense matrix / adjacency growth? Prim (O(V²) matrix or heap Prim).

3. Need k clusters? Build an MST, delete the k−1 heaviest tree edges.

Quantitative check

Kruskal is dominated by sorting: O(E log E). Prim with a binary heap is O(E log V). At V=10⁴, E=5·10⁴ both are fine; at E≈V²/2, matrix Prim O(V²) often wins constant-factor races.

Key properties

•
Exactly V-1 Edges: If there are V vertices, the MST will have exactly V-1 edges (one less than the number of vertices).
•
No Cycles: Adding any edge to an MST creates a cycle.
•
Connected: All vertices are reachable from any other vertex.
•
Multiple MSTs Possible: A graph can have multiple MSTs if edges have equal weights.

🔍 Did You Know?

If all edge weights are distinct, then the MST is unique. This is a sufficient condition, not a necessary one: some graphs with repeated weights still have a unique MST because the tied edges never compete across the same relevant cut.

🔧 Algorithms to Find MST

Algorithm	Approach	Time Complexity	Best For
Prim's	Grows tree from a vertex	O(E log V) heap; O(V²) matrix	Adjacency-driven growth; matrix Prim for dense graphs
Kruskal's	Sorts edges, adds smallest	O(E log E)	Sparse graphs

Interactive cut-property laboratory

Run Prim and Kruskal on the same graph. Watch the active cut, component partition, tie handling, cycle rejection, and cumulative weight: the state an interviewer expects you to explain, not merely code.

MST greedy invariant laboratory

Same safe-edge theorem, two views

Prim grows one cut; Kruskal merges a forest of component cuts.

chosen weight

Step 1 of 6

Seed the tree at A

frontier: A–C(3), A–B(4)

Greedy decision

No edge is chosen yet. The cut is {A} | {B,C,D,E,F}; A–C (3) is the lightest crossing edge.

Invariant / proof obligation

The chosen edges form a tree on the active vertices, and every next choice must cross the active/inactive cut.

Operational state

frontier: A–C(3), A–B(4)

Chosen edges

∅

Keyboard: focus within the lab, then use ← →, Home, or End.

🎯 Key Insight: The V-1 Rule

Why exactly V-1 edges? Think of it this way: You start with V disconnected vertices (V components). Each edge you add merges two components into one. After adding V-1 edges, you've merged all components into a single connected tree! Adding one more edge would create a cycle.

💼 Real World Applications

🌐 Network Design

Designing computer networks, telephone networks, or electrical grids to minimize cable/wire costs while ensuring all nodes are connected.

Example: Connecting office buildings with fiber optic cables

🗺️ Transportation Planning

Planning road networks to connect cities with minimum construction cost, or airline routes to connect airports efficiently.

Example: Highway system connecting major cities

🧬 Clustering

In machine learning, MST can be used for hierarchical clustering by removing the longest edges to form clusters.

Example: Grouping similar customer profiles

🎮 Game Development

Generating random mazes or dungeon layouts by creating an MST and then adding a few extra edges for loops.

Example: Procedural maze generation

Cut property, safety, and extensions

Cut property: for any non-trivial cut, a lightest crossing edge is contained in some MST. If it is the unique lightest crossing edge, it appears in every MST. Cycle property: a uniquely heaviest edge on a cycle appears in no MST; when maximum weights tie, at least one tied maximum can be omitted. These precise forms justify both Prim's and Kruskal's choices without overclaiming under ties.

Disconnected graphs: neither algorithm yields one tree, Kruskal naturally returns a minimum spanning forest (one tree per component). Prim requires a restart per component or an explicit check that all vertices became visited.

Steiner tree vs MST: MST connects all vertices cheaply. If only a subset of terminals must be connected, you need different (generally NP-hard) machinery, that is not MST.

MST is not a shortest-path tree

Minimum spanning tree compared with a single-source shortest-path tree
Question	Minimum spanning tree	Shortest-path tree
Optimizes	Sum of the selected tree edges	Distance from one source to every reachable vertex
Path guarantee	No pairwise shortest-path guarantee	Every source-to-v path in the tree is shortest
Negative edges	Allowed in an undirected MST	Dijkstra forbids them; undirected negative edges also imply a negative two-edge walk
Typical question	“Connect all sites with minimum construction cost”	“Cheapest route from headquarters to each site”

Counterexample intuition: an MST may use one globally cheap chain whose route from a chosen source is long. Replacing it with a more expensive direct edge can improve source distance while increasing total infrastructure cost.

Why the greedy edge is safe: exchange argument

1 · Maintain

Let A be the edges already chosen; assume some MST T contains A.

2 · Choose

Take a lightest edge e crossing a cut that respects A: no edge in A crosses that cut.

3 · Exchange

If T lacks e, adding e creates a cycle. That cycle has another crossing edge f with w(e) ≤ w(f).

4 · Preserve

T − f + e is still spanning and no heavier, so it is an MST containing A ∪ {e}.

Prim's cut is “inside the current tree versus outside.” Kruskal's cut separates any two current DSU components. The algorithms look different operationally but discharge the same proof obligation.

A production-safe Java minimum spanning forest contract

Disconnected input has no spanning tree. This implementation deliberately returns a forest, a component count, and a connectivity flag; it uses long for aggregate cost and deterministic, overflow-safe comparisons.

java

import java.util.*;

public final class MinimumSpanningForest {
    public record Edge(int u, int v, long weight) {}
    public record Result(
            List<Edge> edges, long totalWeight,
            int components, boolean connected) {}

    public static Result kruskalForest(int n, List<Edge> input) {
        if (n < 0) throw new IllegalArgumentException("negative vertex count");

        List<Edge> edges = new ArrayList<>(input);
        for (Edge edge : edges) {
            if (edge.u() < 0 || edge.u() >= n || edge.v() < 0 || edge.v() >= n) {
                throw new IllegalArgumentException("vertex outside [0, n)");
            }
        }
        edges.sort(Comparator.comparingLong(Edge::weight)
                .thenComparingInt(Edge::u)
                .thenComparingInt(Edge::v));

        Dsu dsu = new Dsu(n);
        List<Edge> forest = new ArrayList<>();
        long total = 0L;

        for (Edge edge : edges) {
            if (dsu.union(edge.u(), edge.v())) {
                forest.add(edge);
                total = Math.addExact(total, edge.weight());
                if (forest.size() == Math.max(0, n - 1)) break;
            }
        }

        boolean connected = n == 0 || dsu.components == 1;
        return new Result(List.copyOf(forest), total, dsu.components, connected);
    }

    private static final class Dsu {
        private final int[] parent;
        private final int[] size;
        private int components;

        Dsu(int n) {
            parent = new int[n];
            size = new int[n];
            components = n;
            Arrays.setAll(parent, i -> i);
            Arrays.fill(size, 1);
        }

        int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]]; // path halving
                x = parent[x];
            }
            return x;
        }

        boolean union(int a, int b) {
            int rootA = find(a), rootB = find(b);
            if (rootA == rootB) return false;
            if (size[rootA] < size[rootB]) {
                int temporary = rootA; rootA = rootB; rootB = temporary;
            }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
            components--;
            return true;
        }
    }
}

Recognition clues and edge cases

Signals that say MST

• Connect every location while minimizing total installation cost.
• Choose exactly enough links for connectivity; redundant cycles add no value.
• Cluster into k groups: build an MST, then remove the k−1 largest selected edges.
• Points with implicit geometric distances may require generating edges carefully; a complete edge list costs Θ(V²) memory.

Clarify before coding

• Is the graph undirected? Directed spanning structures are arborescences, a different problem.
• Can it be disconnected? Return a forest or explicitly report “no MST.”
• Are parallel edges, self-loops, negative weights, or equal weights permitted?
• Must output be deterministic, must chosen edges be returned, and can the total exceed 32-bit integer range?

Production lens: normalize undirected endpoints, document duplicate-edge policy, use stable tie-breakers for reproducible builds, validate vertex IDs, avoid subtraction comparators, budget memory for E edges, and test the result independently: acyclic, correct component coverage, and exactly V−components selected edges. Dynamic edge updates generally require more than rerunning textbook code.

Short takeaway

An MST connects every vertex with minimum total weight and no cycles. Trust the cut and cycle properties; pick Prim or Kruskal from graph density and input shape.

Exercises

Draw a cut where two crossing edges share the same lightest weight. Why can more than one MST exist, and which edges are still forced?
Why is a shortest-path tree from an arbitrary root not necessarily an MST? Give a 4-vertex counterexample.
V=2000 dense. Prefer matrix Prim or Kruskal on an explicit edge list of size ~2×10⁶? Justify with big-O and memory.

Primary sources

Cormen et al., CLRS: Minimum spanning trees (cut and cycle properties).
Prim, R. C. (1957); Kruskal, J. B. (1956).
Tarjan: Data structures for Union-Find (Kruskal engineering).