Minimum Spanning Tree

What is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) of a weighted, connected, undirected graph is a subset of edges that:

1. Connects all vertices
2. Has no cycles
3. Has minimum total edge weight

Original Graph:              MST:
  A —1— B                    A —1— B
  |  X  |                     \\     |
  4   2   3                    4   3
  |     |                      \\   |
  C —5— D                      C —5— D

Total weight: 1+4+2+3+5 = 15
MST weight: 1+3+4 = 8 (edges: A-B, B-D, A-C)

Key Properties

• Unique MST: If all edge weights are unique, MST is unique
• |V| - 1 edges: MST always has exactly V-1 edges
• Cut Property: For any cut, the minimum weight edge crossing the cut is in the MST
• Cycle Property: For any cycle, the maximum weight edge is not in the MST

Kruskal's Algorithm

Idea: Sort edges by weight, add edges that don't create cycles.

import java.util.*;

public class KruskalMST {
    
    static class Edge {
        int u, v, weight;
        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }
    
    public List<Edge> kruskal(int n, List<Edge> edges) {
        // Sort edges by weight
        edges.sort(Comparator.comparingInt(e -> e.weight));
        
        UnionFind uf = new UnionFind(n);
        List<Edge> mst = new ArrayList<>();
        
        for (Edge edge : edges) {
            // If adding this edge doesn't create a cycle
            if (uf.union(edge.u, edge.v)) {
                mst.add(edge);
                if (mst.size() == n - 1) break;
            }
        }
        
        return mst;
    }
    
    // Union-Find implementation
    static class UnionFind {
        int[] parent, rank;
        
        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
        
        boolean union(int x, int y) {
            int rootX = find(x), rootY = find(y);
            if (rootX == rootY) return false;
            if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else { parent[rootY] = rootX; rank[rootX]++; }
            return true;
        }
    }
}

Time Complexity: O(E log E) or O(E log V)

Prim's Algorithm

Idea: Start from any vertex, always add the minimum weight edge connecting a visited vertex to an unvisited vertex.

import java.util.*;

public class PrimMST {
    
    static class Edge {
        int to, weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    
    public List<int[]> prim(List<Edge>[] graph, int n) {
        boolean[] inMST = new boolean[n];
        int[] key = new int[n]; // Minimum weight edge to reach this vertex
        int[] parent = new int[n];
        Arrays.fill(key, Integer.MAX_VALUE);
        Arrays.fill(parent, -1);
        key[0] = 0;
        
        // {weight, vertex}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0});
        
        List<int[]> mst = new ArrayList<>();
        
        while (!pq.isEmpty() && mst.size() < n - 1) {
            int[] curr = pq.poll();
            int u = curr[1];
            
            if (inMST[u]) continue;
            inMST[u] = true;
            
            if (parent[u] != -1) {
                mst.add(new int[]{parent[u], u, key[u]});
            }
            
            for (Edge edge : graph[u]) {
                int v = edge.to;
                int weight = edge.weight;
                
                if (!inMST[v] && weight < key[v]) {
                    key[v] = weight;
                    parent[v] = u;
                    pq.offer(new int[]{weight, v});
                }
            }
        }
        
        return mst;
    }
}

Time Complexity: O(E log V) with binary heap

Algorithm Comparison

Aspect	Kruskal's	Prim's
Approach	Edge-centric (sort edges)	Vertex-centric (grow tree)
Data Structure	Union-Find	Priority Queue
Time (binary heap)	O(E log E)	O(E log V)
Best for	Sparse graphs	Dense graphs
Parallelization	Easier	Harder

When to Use Each

Graph Type	Better Algorithm
Sparse (E ≈ V)	Kruskal's
Dense (E ≈ V²)	Prim's
Edge list input	Kruskal's
Adjacency list input	Prim's
Need to check connectivity first	Kruskal's (with Union-Find)

Common MST Applications

1. Minimum Cost to Connect All Points

public int minCostConnectPoints(int[][] points) {
    int n = points.length;
    List<int[]> edges = new ArrayList<>();
    
    // Create all edges with Manhattan distance
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dist = Math.abs(points[i][0] - points[j][0]) 
                     + Math.abs(points[i][1] - points[j][1]);
            edges.add(new int[]{i, j, dist});
        }
    }
    
    // Kruskal's
    edges.sort(Comparator.comparingInt(e -> e[2]));
    UnionFind uf = new UnionFind(n);
    int total = 0;
    int edgesUsed = 0;
    
    for (int[] edge : edges) {
        if (uf.union(edge[0], edge[1])) {
            total += edge[2];
            edgesUsed++;
            if (edgesUsed == n - 1) break;
        }
    }
    
    return total;
}

2. Network Optimization

// Connect cities with minimum cost
public int minimumCost(int n, int[][] connections) {
    List<int[]> edges = new ArrayList<>();
    for (int[] conn : connections) {
        edges.add(new int[]{conn[0] - 1, conn[1] - 1, conn[2]});
    }
    
    edges.sort(Comparator.comparingInt(e -> e[2]));
    UnionFind uf = new UnionFind(n);
    int total = 0;
    int edgesUsed = 0;
    
    for (int[] edge : edges) {
        if (uf.union(edge[0], edge[1])) {
            total += edge[2];
            edgesUsed++;
        }
    }
    
    return edgesUsed == n - 1 ? total : -1;
}

3. Optimize Water Distribution

// kruskal with virtual node for wells
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
    List<int[]> edges = new ArrayList<>();
    
    // Add virtual node 0, edges from wells
    for (int i = 0; i < n; i++) {
        edges.add(new int[]{0, i + 1, wells[i]});
    }
    
    // Add pipe edges
    for (int[] pipe : pipes) {
        edges.add(pipe);
    }
    
    edges.sort(Comparator.comparingInt(e -> e[2]));
    UnionFind uf = new UnionFind(n + 1);
    int total = 0;
    
    for (int[] edge : edges) {
        if (uf.union(edge[0], edge[1])) {
            total += edge[2];
        }
    }
    
    return total;
}

MST Variations

Problem	Variation
Minimum Cost Connect Points	Standard MST
Optimize Water Distribution	Virtual node + MST
Steiner Tree	Not exactly MST (NP-hard)
Second Best MST	Remove each MST edge, find MST

Problem Pattern Recognition

Problem	Key Insight
Connect all points with min cost	MST
Wire all houses	MST
Network optimization	MST
Find redundant connection	MST (cycle detection)
Second minimum spanning tree	MST + edge replacement