Minimum Spanning Tree: Applications and Variants

A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is a subset of edges that connects all vertices with the minimum total edge weight and no cycles. While Kruskal’s and Prim’s algorithms are well-known, the real power of MSTs lies in their wide range of applications and variants.

Quick review: Kruskal’s algorithm

Kruskal’s algorithm sorts edges by weight and greedily adds each edge if it does not form a cycle, using Union-Find for cycle detection.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True


def kruskal(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, list]:
    """
    edges = [(u, v, weight), ...]
    Returns (total_weight, mst_edges).
    """
    edges.sort(key=lambda e: e[2])
    dsu = DSU(n)
    mst_weight = 0
    mst_edges = []

    for u, v, w in edges:
        if dsu.union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
            if len(mst_edges) == n - 1:
                break

    return mst_weight, mst_edges

Time: O(E log E) for sorting, O(E * alpha(V)) for union-find operations.

Space: O(V + E)

Quick review: Prim’s algorithm

Prim’s grows the MST from a starting vertex, always picking the cheapest edge that connects a new vertex.

import heapq

def prim(n: int, adj: list[list[tuple[int, int]]]) -> int:
    """
    adj[u] = [(v, weight), ...]
    Returns total MST weight.
    """
    visited = [False] * n
    min_heap = [(0, 0)]      # (weight, vertex)
    total = 0
    count = 0

    while min_heap and count < n:
        w, u = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        count += 1

        for v, weight in adj[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (weight, v))

    return total

Time: O(E log V) with a binary heap.

Space: O(V + E)

Application 1: network design

MSTs model the problem of connecting all nodes in a network at minimum cost. Examples include:

• Laying cable between offices: each edge weight is the cable cost.
• Road networks: connecting cities with minimum total road length.
• Electrical grids: wiring substations together.
• Water pipelines: connecting all buildings at minimum pipe length.

The MST guarantees the cheapest way to ensure full connectivity. In practice, network designers often add a few extra edges beyond the MST for redundancy, but the MST serves as the baseline minimum cost.

Application 2: clustering with MST

MSTs provide a natural way to cluster data points. The idea: build an MST of all points, then remove the k-1 most expensive edges to create k clusters.

from collections import defaultdict

def mst_clustering(points: list[tuple[float, float]], k: int) -> list[list[int]]:
    """
    Cluster points into k groups using MST.
    Returns list of clusters (each cluster is a list of point indices).
    """
    n = len(points)
    edges = []

    # Build complete graph with Euclidean distances
    for i in range(n):
        for j in range(i + 1, n):
            dx = points[i][0] - points[j][0]
            dy = points[i][1] - points[j][1]
            dist = (dx * dx + dy * dy) ** 0.5
            edges.append((i, j, dist))

    # Sort and build MST
    edges.sort(key=lambda e: e[2])
    dsu = DSU(n)
    mst_edges = []

    for u, v, w in edges:
        if dsu.union(u, v):
            mst_edges.append((u, v, w))

    # Remove k-1 most expensive MST edges
    mst_edges.sort(key=lambda e: e[2], reverse=True)
    cluster_dsu = DSU(n)

    for u, v, w in mst_edges[k - 1:]:
        cluster_dsu.union(u, v)

    # Group by root
    clusters = defaultdict(list)
    for i in range(n):
        clusters[cluster_dsu.find(i)].append(i)

    return list(clusters.values())

This is equivalent to single-linkage hierarchical clustering and runs in O(n^2 log n) for n points with a complete graph.

Why does this work?

The MST connects all points with minimum total distance. The most expensive edges in the MST bridge the most distant clusters. Removing these edges naturally separates the points into well-separated groups.

Minimum cost to connect all points (LeetCode 1584)

Given n points where cost(i, j) = |xi - xj| + |yi - yj| (Manhattan distance), find the minimum cost to connect all points.

This is a direct MST problem. With n up to 1000, the O(n^2) approach of building all edges and running Prim works well.

def min_cost_connect_points(points: list[list[int]]) -> int:
    """
    LeetCode 1584: Minimum Cost to Connect All Points.
    Uses Prim's algorithm optimized for dense graphs.
    """
    n = len(points)
    if n <= 1:
        return 0

    # Prim's with O(n^2) array-based approach for dense graphs
    visited = [False] * n
    min_cost = [float('inf')] * n
    min_cost[0] = 0
    total = 0

    for _ in range(n):
        # Find unvisited vertex with minimum cost
        u = -1
        for v in range(n):
            if not visited[v] and (u == -1 or min_cost[v] < min_cost[u]):
                u = v

        visited[u] = True
        total += min_cost[u]

        # Update costs to all unvisited vertices
        for v in range(n):
            if not visited[v]:
                dist = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                min_cost[v] = min(min_cost[v], dist)

    return total

Time: O(n^2) — optimal for dense graphs where E = O(n^2).

Space: O(n)

Second-best MST

The second-best MST has the smallest total weight among all spanning trees except the MST itself. It can be found by:

1. Build the MST.
2. For each non-MST edge (u, v, w), find the maximum weight edge on the MST path from u to v.
3. Swap: remove the max-weight MST edge, add (u, v, w).
4. The swap that increases total weight the least gives the second-best MST.

from collections import defaultdict, deque

def second_best_mst(n: int, edges: list[tuple[int, int, int]]) -> int:
    """
    Returns the weight of the second-best MST.
    """
    # Step 1: Build MST using Kruskal
    sorted_edges = sorted(edges, key=lambda e: e[2])
    dsu = DSU(n)
    mst_edges = set()
    mst_adj = defaultdict(list)
    mst_weight = 0

    for u, v, w in sorted_edges:
        if dsu.union(u, v):
            mst_edges.add((min(u, v), max(u, v), w))
            mst_adj[u].append((v, w))
            mst_adj[v].append((u, w))
            mst_weight += w

    # Step 2: For each non-MST edge, find max weight on MST path (BFS)
    def max_on_path(src: int, dst: int) -> int:
        """BFS to find maximum edge weight on MST path from src to dst."""
        visited = [False] * n
        queue = deque([(src, 0)])
        visited[src] = True

        while queue:
            node, max_w = queue.popleft()
            if node == dst:
                return max_w

            for nbr, w in mst_adj[node]:
                if not visited[nbr]:
                    visited[nbr] = True
                    queue.append((nbr, max(max_w, w)))

        return 0

    # Step 3: Try all non-MST edges, find minimum weight increase
    best_increase = float('inf')

    for u, v, w in sorted_edges:
        key = (min(u, v), max(u, v), w)
        if key not in mst_edges:
            max_w = max_on_path(u, v)
            if w - max_w > 0:
                best_increase = min(best_increase, w - max_w)

    return mst_weight + best_increase

Time: O(E * V) with BFS for each non-MST edge. Can be optimized to O(V^2) with LCA + sparse table.

Why the swap works

By the cycle property of MSTs, the heaviest edge in any cycle cannot be in the MST. When we add a non-MST edge (u, v, w), it creates a cycle with the MST path from u to v. Removing the heaviest edge on that path gives a valid spanning tree. The minimum such swap produces the second-best MST.

Critical and pseudo-critical edges (LeetCode 1489)

An edge is critical if removing it increases the MST weight (or disconnects the graph). An edge is pseudo-critical if it appears in at least one MST but not all of them.

def find_critical_and_pseudo_critical_edges(
    n: int, edges: list[list[int]]
) -> list[list[int]]:
    """
    LeetCode 1489: Find Critical and Pseudo-Critical Edges in MST.
    """
    # Add original indices
    indexed_edges = [(u, v, w, i) for i, (u, v, w) in enumerate(edges)]
    indexed_edges.sort(key=lambda e: e[2])

    def build_mst(n, edges, skip=-1, force_edge=None):
        """Build MST, optionally skipping an edge or forcing one."""
        dsu = DSU(n)
        weight = 0
        count = 0

        if force_edge is not None:
            u, v, w, _ = force_edge
            dsu.union(u, v)
            weight += w
            count += 1

        for i, (u, v, w, idx) in enumerate(edges):
            if i == skip:
                continue
            if dsu.union(u, v):
                weight += w
                count += 1

        if count < n - 1:
            return float('inf')
        return weight

    base_mst = build_mst(n, indexed_edges)
    critical = []
    pseudo_critical = []

    for i, (u, v, w, idx) in enumerate(indexed_edges):
        # Check critical: skip this edge, does MST weight increase?
        if build_mst(n, indexed_edges, skip=i) > base_mst:
            critical.append(idx)
        # Check pseudo-critical: force this edge, does MST weight stay same?
        elif build_mst(n, indexed_edges, force_edge=indexed_edges[i]) == base_mst:
            pseudo_critical.append(idx)

    return [critical, pseudo_critical]

Time: O(E^2 * alpha(V)) — for each edge, rebuild MST.

Space: O(V + E)

Understanding the logic

• Critical test: Remove the edge and rebuild. If the new MST costs more (or the graph disconnects), the edge is critical.
• Pseudo-critical test: Force the edge into the MST. If the total cost matches the original MST, the edge can appear in some MST (pseudo-critical). If the cost is higher, it never appears in any MST.

When to use Kruskal vs Prim

Criterion	Kruskal	Prim
Graph density	Sparse (E ~ V)	Dense (E ~ V^2)
Data structure	Edge list + DSU	Adjacency list + heap
Time complexity	O(E log E)	O(E log V)
Easier to modify	Yes (edge filtering)	Yes (priority updates)
Dense graph, no heap	Not ideal	O(V^2) with array

For competitive programming, Kruskal with DSU is usually simpler to implement. For dense graphs with adjacency matrix input, Prim with an array-based approach (O(V^2)) avoids sorting all edges.

Boruvka’s algorithm

A lesser-known MST algorithm that works well for parallel computation. Each iteration, every component finds its cheapest outgoing edge and adds it. The number of components halves each round.

def boruvka(n: int, edges: list[tuple[int, int, int]]) -> int:
    """
    Boruvka's MST algorithm.
    Returns total MST weight.
    """
    dsu = DSU(n)
    mst_weight = 0
    num_components = n

    while num_components > 1:
        # cheapest[comp] = (weight, u, v)
        cheapest = [None] * n

        for u, v, w in edges:
            ru, rv = dsu.find(u), dsu.find(v)
            if ru == rv:
                continue
            if cheapest[ru] is None or w < cheapest[ru][0]:
                cheapest[ru] = (w, u, v)
            if cheapest[rv] is None or w < cheapest[rv][0]:
                cheapest[rv] = (w, u, v)

        for i in range(n):
            if cheapest[i] is not None:
                w, u, v = cheapest[i]
                if dsu.union(u, v):
                    mst_weight += w
                    num_components -= 1

    return mst_weight

Time: O(E log V) — at most O(log V) rounds, each scanning all edges.

Space: O(V + E)

MST properties to remember

1. Cut property: The lightest edge crossing any cut must be in the MST.
2. Cycle property: The heaviest edge in any cycle cannot be in the MST (assuming unique weights).
3. Uniqueness: If all edge weights are distinct, the MST is unique.
4. Number of edges: An MST of n vertices always has exactly n - 1 edges.
5. Subgraph property: Restricting the full MST to a subset of vertices does not necessarily give the MST of the subgraph.

Big-O summary

Algorithm / Variant	Time	Space
Kruskal	O(E log E)	O(V+E)
Prim (binary heap)	O(E log V)	O(V+E)
Prim (array, dense)	O(V^2)	O(V)
Boruvka	O(E log V)	O(V+E)
Second-best MST (naive)	O(E * V)	O(V+E)
Critical edges (naive)	O(E^2 alpha)	O(V+E)

Practice problems

Problem	Difficulty	Key Concept
Min Cost to Connect All Points - LeetCode 1584	Medium	Direct MST on Manhattan distances
Find Critical and Pseudo-Critical Edges - LeetCode 1489	Hard	Edge classification in MST
Connecting Cities With Minimum Cost - LeetCode 1135	Medium	Straightforward Kruskal
Optimize Water Distribution - LeetCode 1168	Hard	Virtual node + MST
Minimum Spanning Tree - CSES	Medium	Standard MST with Kruskal

Key takeaways

• MSTs solve network design problems optimally: minimum cost to connect all nodes.
• Removing the k-1 heaviest MST edges produces k natural clusters (single-linkage clustering).
• The second-best MST is found by swapping one non-MST edge with the heaviest edge on its MST path.
• Critical edges appear in every MST; pseudo-critical edges appear in at least one but not all.
• Choose Kruskal for sparse graphs and Prim for dense ones. Use Boruvka when parallelism matters.