Minimum Spanning Tree

What is a Spanning Tree?

A spanning tree of a connected undirected graph is a subgraph that includes all vertices and is a tree (connected, acyclic). A graph with V vertices has a spanning tree with exactly V-1 edges.

A Minimum Spanning Tree (MST) is a spanning tree with the minimum total edge weight. MSTs are used in network design, clustering, and approximation algorithms.

Algorithm	Approach	Time	Best for
Kruskal's	Greedy â€” sort edges, add if no cycle	O(E log E)	Sparse graphs
Prim's	Greedy â€” grow tree from a vertex	O((V + E) log V)	Dense graphs

Kruskal's and Prim's MST Algorithms

import java.util.*;

public class Kruskal {

    // Union-Find (Disjoint Set Union) for cycle detection
    static int[] parent, rank;

    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);  // path compression
        return parent[x];
    }

    static boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;  // same component â†’ cycle!
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
        return true;
    }

    // Kruskal's MST â€” O(E log E)
    static int kruskal(int V, int[][] edges) {
        parent = new int[V]; rank = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;

        // Sort edges by weight
        Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));

        int mstWeight = 0, edgesUsed = 0;
        System.out.println("MST edges (Kruskal):");
        for (int[] edge : edges) {
            if (union(edge[0], edge[1])) {
                System.out.println("  " + edge[0] + " - " + edge[1] + " : " + edge[2]);
                mstWeight += edge[2];
                if (++edgesUsed == V - 1) break;
            }
        }
        return mstWeight;
    }

    public static void main(String[] args) {
        int V = 4;
        int[][] edges = {{0,1,10},{0,2,6},{0,3,5},{1,3,15},{2,3,4}};
        System.out.println("MST weight: " + kruskal(V, edges));
        // MST: 2-3:4, 0-3:5, 0-1:10 â†’ weight 19
    }
}

import java.util.*;

public class Prim {

    // Prim's MST â€” O((V + E) log V) with priority queue
    static int prim(int V, List<int[]>[] adj) {
        boolean[] inMST = new boolean[V];
        int[] key = new int[V];  // minimum weight edge to include vertex
        Arrays.fill(key, Integer.MAX_VALUE);
        key[0] = 0;

        // Min-heap: {key, vertex}
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, 0});

        int mstWeight = 0;
        System.out.println("MST edges (Prim):");

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[1];
            if (inMST[u]) continue;
            inMST[u] = true;
            mstWeight += curr[0];

            for (int[] edge : adj[u]) {
                int v = edge[0], w = edge[1];
                if (!inMST[v] && w < key[v]) {
                    key[v] = w;
                    pq.offer(new int[]{w, v});
                    System.out.println("  " + u + " - " + v + " : " + w);
                }
            }
        }
        return mstWeight;
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        int V = 5;
        List<int[]>[] adj = new ArrayList[V];
        for (int i = 0; i < V; i++) adj[i] = new ArrayList<>();

        int[][] edges = {{0,1,2},{0,3,6},{1,2,3},{1,3,8},{1,4,5},{2,4,7},{3,4,9}};
        for (int[] e : edges) {
            adj[e[0]].add(new int[]{e[1], e[2]});
            adj[e[1]].add(new int[]{e[0], e[2]});
        }

        System.out.println("MST weight: " + prim(V, adj));  // 16
    }
}

Properties of MST

A graph with V vertices has an MST with exactly V-1 edges
MST is unique if all edge weights are distinct
MST is not unique if some edges have equal weights
The MST of a graph is a subgraph â€” it uses only existing edges
Removing any edge from an MST disconnects the graph

Union-Find (Disjoint Set Union)

Kruskal's algorithm uses Union-Find to efficiently detect cycles. It maintains a collection of disjoint sets and supports two operations:

find(x) â€” returns the representative (root) of x's set
union(x, y) â€” merges the sets containing x and y

With path compression and union by rank, both operations run in nearly O(1) amortized time (O(α(n)) where α is the inverse Ackermann function).

MST Applications

Network design â€” minimum cost to connect all computers/cities
Cluster analysis â€” remove the k-1 most expensive MST edges to get k clusters
Approximation algorithms â€” 2-approximation for TSP using MST
Image segmentation â€” group pixels by similarity
Circuit design â€” minimize wire length connecting components

Minimum Spanning Tree

What is a Spanning Tree?

Properties of MST

Union-Find (Disjoint Set Union)

MST Applications

Ready to Level Up Your Skills?