Kruskal Algorithm

You have a network of cities. Roads connect them, each with a construction cost. You need to connect every city while spending as little as possible. No loops allowed.

That's the Minimum Spanning Tree problem. Kruskal's algorithm solves it with a greedy strategy: always pick the cheapest edge that doesn't create a cycle.

The intuition

Sort all edges by weight. Walk through them cheapest-first. For each edge, ask: "Does adding this edge connect two previously disconnected components?" If yes, keep it. If it would form a cycle, skip it.

The key data structure here is Union-Find (also called Disjoint Set). It lets you quickly check whether two nodes are already connected and merge components in near-constant time.

The code

class UnionFind {
    constructor(size) {
        this.parent = Array.from({ length: size }, (_, i) => i);
        this.rank = new Array(size).fill(0);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX === rootY) return false;

        if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
        } else if (this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
        } else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }
        return true;
    }
}

function kruskal(vertices, edges) {
    edges.sort((a, b) => a.weight - b.weight);
    const uf = new UnionFind(vertices);
    const mst = [];

    for (const edge of edges) {
        if (uf.union(edge.from, edge.to)) {
            mst.push(edge);
            if (mst.length === vertices - 1) break;
        }
    }

    return mst;
}

Complexity

• Time: O(E log E) — dominated by sorting the edges.
• Space: O(V) — for the Union-Find structure.

Trade-offs

Kruskal's is great when you have a sparse graph (few edges relative to vertices). For dense graphs, Prim's algorithm with a priority queue is usually faster. Kruskal's also needs all edges up front — it can't work on a graph that's being discovered incrementally.