Minimum Spanning Trees (MST)

1. Introduction: The Cheapest Network

Imagine you are a civil engineer tasked with connecting 10 isolated cities with roads. Building roads is incredibly expensive, and the cost varies depending on the distance between specific cities. Your goal is to connect all 10 cities so that every city is reachable from every other city, while minimizing the total cost of asphalt.

You don't need to build a road between every single city. You just need enough roads to form a connected network. Mathematically, to connect $V$ vertices, you strictly need $V - 1$ edges. A graph that connects all nodes with no cycles is called a Spanning Tree. The one with the lowest total edge weight is the Minimum Spanning Tree (MST).

2. Core Concept: Kruskal's vs Prim's

There are two elite Greedy Algorithms used to find an MST. Both guarantee the exact same minimum cost.

1. Kruskal's Algorithm (Edge-Focused): Sort all edges in the graph from cheapest to most expensive. Greedily pick the cheapest edge. If it forms a cycle, throw it away. If it doesn't, add it to the MST. Repeat until you have $V-1$ edges. (Requires a Union-Find data structure).
2. Prim's Algorithm (Vertex-Focused): Start at any arbitrary node. Look at all edges connecting your current connected component to unvisited nodes. Pick the cheapest one. Repeat until all nodes are visited. (Requires a Priority Queue / Min-Heap).

Rule of Thumb: Use Kruskal's for Sparse Graphs (few edges). Use Prim's for Dense Graphs (many edges).

3. Advanced Code Example: Kruskal's Algorithm

Problem Statement: (LeetCode 1584) Min Cost to Connect All Points. You are given an array points representing integer coordinates of some points on a 2D-plane. The cost of connecting two points is the Manhattan distance between them. Return the minimum cost to make all points connected.

The Insight: This is a classic MST problem. We will build a list of all possible edges between all points, sort them by cost, and use Union-Find to safely pick edges without creating cycles.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class KruskalsAlgorithm {
    // Edge class
    static class Edge implements Comparable<Edge> {
        int u, v, weight;
        public Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge other) {
            return Integer.compare(this.weight, other.weight);
        }
    }
    
    // Union-Find (Disjoint Set) class
    static class UnionFind {
        int[] parent;
        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        
        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]); // Path compression
        }
        
        // Returns true if union was successful (no cycle)
        public boolean union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI == rootJ) return false; // Cycle detected!
            parent[rootI] = rootJ;
            return true;
        }
    }

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<Edge> edges = new ArrayList<>();
        
        // 1. Build all possible edges O(N^2)
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cost = Math.abs(points[i][0] - points[j][0]) + 
                           Math.abs(points[i][1] - points[j][1]);
                edges.add(new Edge(i, j, cost));
            }
        }
        
        // 2. Sort edges by weight
        Collections.sort(edges);
        
        // 3. Kruskal's algorithm
        UnionFind uf = new UnionFind(n);
        int totalCost = 0;
        int edgesUsed = 0;
        
        for (Edge edge : edges) {
            if (uf.union(edge.u, edge.v)) {
                totalCost += edge.weight;
                edgesUsed++;
                if (edgesUsed == n - 1) break; // MST complete!
            }
        }
        
        return totalCost;
    }
}

Complexity Analysis:

• Time Complexity: $O(E \log E)$. Building edges takes $O(V^2)$. Sorting takes $O(E \log E)$. The Union-Find operations take $O(E \alpha(V)) \approx O(E)$. Total time is dominated by sorting.
• Space Complexity: $O(E)$ to store the edge list, plus $O(V)$ for the Union-Find array.

4. Advanced Code Example: Prim's Algorithm

Let's solve the exact same problem using Prim's Algorithm.

The Insight: Instead of pre-calculating and sorting every single edge, we start at point 0. We add all of point 0's edges to a Min-Heap. We pop the smallest edge. If the destination node is unvisited, we add the cost, mark it visited, and push all of its edges into the Min-Heap.

import java.util.PriorityQueue;

public class PrimsAlgorithm {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        boolean[] visited = new boolean[n];
        
        // Array format: [destination_node, edge_weight]
        minHeap.offer(new int[]{0, 0}); 
        
        int totalCost = 0;
        int edgesUsed = 0;
        
        while (edgesUsed < n) {
            int[] current = minHeap.poll();
            int u = current[0];
            int weight = current[1];
            
            // Cycle prevention! If already visited, ignore this edge.
            if (visited[u]) continue; 
            
            visited[u] = true;
            totalCost += weight;
            edgesUsed++;
            
            // Add all edges from this new node to unvisited nodes
            for (int v = 0; v < n; v++) {
                if (!visited[v]) {
                    int cost = Math.abs(points[u][0] - points[v][0]) + 
                               Math.abs(points[u][1] - points[v][1]);
                    minHeap.offer(new int[]{v, cost});
                }
            }
        }
        
        return totalCost;
    }
}

Complexity Analysis:

• Time Complexity: $O(E \log V)$. In the worst case, we push every edge into the heap. The heap has a max size of $E$. (In a dense graph where $E = V^2$, Kruskal's and Prim's perform similarly, but Prim's avoids building the massive object list first).
• Space Complexity: $O(E)$ for the Priority Queue.

5. Common Mistakes Beginners Make

1. Confusing MST with Shortest Path (Dijkstra's)

   • The Mistake: Using Dijkstra's to find the Minimum Spanning Tree.
   • Why it's wrong: Dijkstra's finds the shortest path from one specific node to all other nodes. An MST minimizes the total weight of the entire network. If A connects to B (cost 100), and B connects to C (cost 2), the MST uses both edges (total 102). Dijkstra's from A to C might prefer a direct edge A to C (cost 99), even though it ignores B entirely! They solve fundamentally different problems.

2. Forgetting Path Compression in Kruskal's

   • The Mistake: Writing public int find(int i) { if (parent[i] == i) return i; return find(parent[i]); }
   • Why it's wrong: Without path compression (parent[i] = find(...)), a skewed Union-Find tree takes $O(V)$ time per find, degrading Kruskal's to $O(V^2)$ for cycle detection. Path compression guarantees amortized $O(1)$ time.

3. Not tracking visited nodes when popping from Prim's Heap

   • The Mistake: Only checking !visited[v] when pushing to the heap, but not when popping.
   • Why it's wrong: Multiple nodes can push an edge to the SAME unvisited node with different costs. If Node 5 is visited via the cheapest edge, the more expensive edges to Node 5 are still sitting in the heap! You must if (visited[u]) continue; immediately after popping to ignore these stale edges.

6. Interview Q&A

Q1: If all edge weights are unique, does the graph have a unique MST? Answer: Yes. This is a fundamental mathematical property of graphs. If all edge weights are distinct, there is exactly one unique Minimum Spanning Tree.

Q2: Can MST algorithms handle negative edge weights? Answer: Yes! Unlike Dijkstra's algorithm (which fails with negative edges because its greedy assumption relies on distances only increasing), both Kruskal's and Prim's work perfectly with negative weights. The logic of picking the "most negative" edge first is completely valid for Spanning Trees.

Q3: Which algorithm is easier to write in an interview? Answer: If you have the Union-Find template memorized, Kruskal's is generally less prone to infinite loops and easier to reason about. However, Prim's is just a slight modification of Dijkstra's template. If you know Dijkstra's perfectly, Prim's might be faster to code.

7. Practice Problems

1. Min Cost to Connect All Points (LeetCode 1584)
   • Goal: Implement both Kruskal's and Prim's algorithms and compare their runtimes.
2. Network Delay Time (LeetCode 743)
   • Hint: This is NOT an MST problem, it's Dijkstra's! Do it to understand the difference.
3. Connecting Cities With Minimum Cost (LeetCode 1135 / Premium)
   • Goal: A pure standard MST implementation on an Adjacency List.

8. Summary

• MST Goal: Connect all $V$ nodes using exactly $V - 1$ edges with the absolute minimum total cost.
• Kruskal's Algorithm: Sort edges. Pick cheapest. Use Union-Find to prevent cycles. (Best for sparse graphs).
• Prim's Algorithm: Start at Node 0. Use a Min-Heap to greedily pick the cheapest edge connected to your current visited component. (Best for dense graphs).
• Difference from Dijkstra's: Dijkstra's tracks the cumulative sum from the start node. Prim's tracks the absolute weight of the individual edge.

Advanced Code Implementations

// Example: Kruskal's Algorithm with Disjoint Set Union (DSU)
import java.util.*;

public class KruskalMST {
    class DSU {
        int[] parent, rank;
        DSU(int n) {
            parent = new int[n]; rank = new int[n];
            for(int i=0; i<n; i++) parent[i] = i;
        }
        int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        boolean union(int i, int j) {
            int rootI = find(i), rootJ = find(j);
            if (rootI != rootJ) {
                if (rank[rootI] < rank[rootJ]) parent[rootI] = rootJ;
                else if (rank[rootI] > rank[rootJ]) parent[rootJ] = rootI;
                else { parent[rootJ] = rootI; rank[rootI]++; }
                return true;
            }
            return false;
        }
    }
    
    public int minimumCost(int n, int[][] connections) {
        Arrays.sort(connections, (a, b) -> a[2] - b[2]);
        DSU dsu = new DSU(n + 1);
        int cost = 0, edges = 0;
        for (int[] conn : connections) {
            if (dsu.union(conn[0], conn[1])) {
                cost += conn[2];
                edges++;
                if (edges == n - 1) return cost;
            }
        }
        return -1;
    }
}

// Example: Prim's Algorithm using Priority Queue
import java.util.*;

public class PrimMST {
    public int minimumCost(int n, int[][] connections) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int[] conn : connections) {
            adj.get(conn[0]).add(new int[]{conn[1], conn[2]});
            adj.get(conn[1]).add(new int[]{conn[0], conn[2]});
        }
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.add(new int[]{1, 0}); // Start from node 1 with cost 0
        boolean[] visited = new boolean[n + 1];
        int cost = 0, edges = 0;
        
        while (!pq.isEmpty() && edges < n) {
            int[] curr = pq.poll();
            int u = curr[0], w = curr[1];
            if (visited[u]) continue;
            visited[u] = true;
            cost += w;
            edges++;
            
            for (int[] neighbor : adj.get(u)) {
                if (!visited[neighbor[0]]) {
                    pq.add(neighbor);
                }
            }
        }
        return edges == n ? cost : -1;
    }
}

Expanded Interview Q&A

Q1: What is a Minimum Spanning Tree?

Answer: A subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Q2: When is Kruskal's algorithm preferred over Prim's?

Answer: Kruskal's is better for sparse graphs because its time complexity depends heavily on sorting the edges. Prim's is often better for dense graphs.

Q3: What is the time complexity of Kruskal's algorithm?

Answer: O(E log E) or O(E log V) to sort the edges. The DSU operations take near O(1) time.

Q4: Why do we use Union by Rank and Path Compression in DSU?

Answer: They flatten the tree and ensure operations take nearly O(1) time (Inverse Ackermann function), drastically speeding up the union and find operations.

Q5: Can a graph have multiple Minimum Spanning Trees?

Answer: Yes, if there are edges with identical weights, there can be multiple distinct MSTs, though they will all have the same total minimum weight.