Minimum Spanning Tree (Kruskal & Prim)

A Minimum Spanning Tree (MST) connects every vertex in a weighted, undirected graph using the minimum possible total edge weight, with no cycles. Think of laying network cable between offices: you need every office connected to the network somehow, you want to minimize total cable cost, and there's never a reason to connect two offices that are already connected through some other path — that would just be wasted cable forming a cycle. This lesson covers the two classic ways to build one: Kruskal's algorithm and Prim's algorithm.

The Example Graph

Both algorithms below run on this same 5-vertex weighted graph:

Kruskal's Algorithm

Kruskal's is greedy at the level of individual edges: sort all edges by weight, then walk them from cheapest to most expensive, adding each edge to the MST unless it would create a cycle (i.e., unless both endpoints are already connected to each other through edges already chosen).

"Already connected" is checked with a Union-Find (Disjoint Set) structure: each vertex starts in its own group; find() tells you which group a vertex belongs to, and union() merges two groups. Two vertices in the same group already have a path between them, so adding an edge between them would only create a cycle.

class UnionFind {
    int[] parent;

    UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;              // every vertex starts as its own group
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // path compression: flatten the chain as we go
        }
        return parent[x];
    }

    boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;             // already connected -- adding this edge would create a cycle
        }
        parent[rootX] = rootY;          // merge the two groups
        return true;
    }
}

class Edge {
    int from, to, weight;
    Edge(int from, int to, int weight) {
        this.from = from; this.to = to; this.weight = weight;
    }
}

public static int kruskalMST(int n, List<Edge> edges) {
    edges.sort((a, b) -> a.weight - b.weight);   // cheapest edges first
    UnionFind uf = new UnionFind(n);
    int totalWeight = 0;
    int edgesUsed = 0;

    for (Edge e : edges) {
        if (uf.union(e.from, e.to)) {   // true means no cycle -- safe to add
            totalWeight += e.weight;
            edgesUsed++;
            if (edgesUsed == n - 1) {
                break;                 // MST complete: n vertices need exactly n-1 edges
            }
        }
    }
    return totalWeight;
}

On the example graph (A=0, B=1, C=2, D=3, E=4): sorted edges are A-B(2), B-C(3), D-E(4), B-E(5), A-C(6), C-E(7), B-D(8). Add A-B(2) — no cycle. Add B-C(3) — no cycle. Add D-E(4) — no cycle. Add B-E(5) — no cycle, and now 4 edges are used (n-1 = 4), so we stop. Skip everything after. MST edges: {A-B, B-C, D-E, B-E}, total weight = 2+3+4+5 = 14.

Time complexity: O(E log E) — dominated by sorting the edges; the Union-Find operations with path compression are nearly O(1) amortized. Space complexity: O(V + E) — the Union-Find parent array (O(V)) plus storing the edge list (O(E)).

Prim's Algorithm

Prim's is greedy at the level of vertices: start from any single vertex, and repeatedly grow the tree by adding the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree. This is structurally the same shape as Dijkstra's algorithm — a min-heap of candidate edges, always expanding via the cheapest option — except Prim's compares edge weights to grow a tree, while Dijkstra compares cumulative path distances to find shortest paths.

class Edge {
    int to, weight;
    Edge(int to, int weight) {
        this.to = to; this.weight = weight;
    }
}

public static int primMST(int n, Map<Integer, List<Edge>> adj, int start) {
    boolean[] inMST = new boolean[n];
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // [vertex, weight], ordered by weight
    minHeap.offer(new int[]{start, 0});
    int totalWeight = 0;

    while (!minHeap.isEmpty()) {
        int[] current = minHeap.poll();
        int vertex = current[0];
        int weight = current[1];
        if (inMST[vertex]) {
            continue;                    // already in the tree via a cheaper edge -- skip
        }
        inMST[vertex] = true;
        totalWeight += weight;

        for (Edge e : adj.get(vertex)) {
            if (!inMST[e.to]) {
                minHeap.offer(new int[]{e.to, e.weight});  // candidate edge to grow the tree further
            }
        }
    }
    return totalWeight;
}

Starting from A on the same graph: pop A (weight 0), mark in MST, push A-B(2) and A-C(6). Pop B(2), mark in MST, totalWeight=2, push B-C(3), B-D(8), B-E(5). Pop B-C(3) (cheapest available), mark C in MST, totalWeight=5, push C-E(7) (A-C(6) still sits in the heap but leads to an already-visited vertex once popped). Pop B-E(5), mark E in MST, totalWeight=10, push D-E(4) — this replaces the need for B-D(8). Pop D-E(4), mark D in MST, totalWeight=14. Same MST edges and same total weight as Kruskal's found, just discovered in a different order — this is expected, since for a graph with distinct edge weights the MST is unique.

Time complexity: O(E log V) using a binary heap — every edge may be pushed onto the heap once (O(log V) per push/pop), similar to Dijkstra's complexity with a heap. Space complexity: O(V + E) — the adjacency list (O(V + E)) plus the heap, which holds at most O(E) candidate edges.

Kruskal vs Prim: When to Use Which