Kruskal's Algorithm

Kruskal's algorithm builds a minimum spanning tree (MST) by sorting all edges by weight and adding them one by one, skipping an edge if it would form a cycle. [Union Find](/blog/algorithms/union-find/union-find-basics) (disjoint set) is used to detect cycles in almost constant time per operation.

When to Use

  • Find a minimum spanning tree of a connected, undirected, weighted graph.
  • Same goal as Prim; Kruskal is often easier to implement when you have a list of edges.
  • Good for sparse graphs (few edges); sorting edges is O(E log E).

Core Idea

  1. Sort all edges by weight (ascending).
  2. Initialize Union Find with each node in its own set.
  3. For each edge (u, v, w) in sorted order:
    • If u and v are in different components (find(u) != find(v)), add the edge to the MST and union(u, v).
    • Otherwise skip (would form a cycle).
  4. Stop when the MST has V - 1 edges.

Java Implementation

Java
// Edge: [u, v, weight]
int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);
    UnionFind uf = new UnionFind(n);
    int totalCost = 0;
    int edgesAdded = 0;

    for (int[] e : edges) {
        if (edgesAdded == n - 1) break;
        int u = e[0], v = e[1], w = e[2];
        if (uf.find(u) != uf.find(v)) {
            uf.union(u, v);
            totalCost += w;
            edgesAdded++;
        }
    }
    return edgesAdded == n - 1 ? totalCost : -1; // -1 if disconnected
}

// Union Find with path compression and union by rank
class UnionFind {
    private 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];
    }

    void union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }
    }
}

Time Complexity

  • Time: O(E log E) for sorting edges plus O(E · α(V)) for Union Find operations (α is inverse Ackermann, effectively constant). Dominated by sort: O(E log E).
  • Space: O(V) for Union Find.

Prim vs Kruskal

  • Kruskal: sort edges, then scan with [Union Find](/blog/algorithms/union-find/union-find-basics). Simple and good for sparse graphs.
  • [Prim's Algorithm](/blog/algorithms/minimum-spanning-tree/prim): grow from one node with a min-heap. Good when you have an adjacency list and dense graphs.

Both yield an MST with the same total weight.

Summary

Kruskal builds an MST by sorting edges by weight and adding each edge if it connects two different components (use Union Find to check). Stop when you have V - 1 edges. Simple to code and efficient for sparse graphs.