Kruskal’s algorithm: minimum spanning tree

One network with minimum total weight

A spanning tree includes every vertex of a connected undirected graph and contains no cycles. On V vertices it has V−1 edges. A minimum spanning tree minimizes their total weight; it need not provide shortest routes from any chosen vertex.

Kruskal has no start vertex. Initially every vertex is a separate component, including isolated vertices. An accepted edge joins two components. If the input is disconnected, the result is a minimum spanning forest: one tree for each connected component.

Sort globally, reject cycles

Sort all edges by weight, then consider them in that order. If an edge’s endpoints belong to different components, accept it and merge those components. If the endpoints already belong to one component, skip the edge: the existing forest already contains a path between them, so adding it would close a cycle.

For equal weights, the player uses the original edge index. This makes the run reproducible; a different tie order can produce a different minimum tree of the same weight. Once only one component remains, the tree is complete and unexamined edges are marked as unnecessary, rather than rejected. If several components remain, continue until the edge list is exhausted.

The same graph as Prim, a different order

The default order is B—C = 1, A—C = 2, D—E = 2, A—B = 4, C—E = 5, B—D = 7, C—D = 8. First take B—C, then A—C. Next take D—E, forming a separate small tree. Kruskal can grow several trees at once.

Skip A—B = 4: A and B are already connected through C. Take C—E = 5 to join the two trees. The result is four edges with weight 1 + 2 + 2 + 5 = 10. The remaining edges need no inspection. Prim on this graph starts at A and chooses A—C, C—B, C—E, E—D; both runs yield the same minimum weight.

How do we know whether two vertices are connected?

A disjoint-set union structure, or DSU, represents each component as a tree of parent pointers. find(v) follows these pointers to a representative. Equal representatives mean the vertices are already connected. For different representatives, union links the smaller tree under the larger one.

This implementation also compresses paths by pointing a vertex to its grandparent while searching. DSU parent links are auxiliary data, not edges of the graph or the resulting spanning tree. The component groups shown below the graph list actual connected vertices; their display label is the smallest vertex index, not a DSU root.

Why taking this edge is safe

The chosen edges form a forest that can be extended to a minimum spanning forest. For a candidate joining two current components, consider the cut separating one of them from all other vertices. No lighter crossing edge can remain unprocessed; a previously processed crossing edge would already have merged these components. Thus the candidate is a lightest edge across that cut.

Take a minimum forest containing all edges already selected. If it lacks the candidate, adding the candidate creates a cycle with another edge crossing the same cut. That other edge is no lighter. Exchanging them preserves a minimum forest containing the new choice. Each successful merge decreases the component count by one, so at every stage selected edges = V − current components.

Negative weights and disconnected inputs

Negative and zero weights are allowed: we compare edge weights, rather than tentative route distances. The forest must still have no cycles, even if all edges of a cycle are negative. With equal weights a minimum forest may not be unique.

The negative preset changes B—C to −3 and D—E to zero; the result weighs four. The disconnected preset has groups A,B,C and D,E: the result has two components, three edges and weight five. A single isolated vertex is already a tree of weight zero.

Read and control the player

Green edges form the selected forest. Amber highlights the edge under consideration and its endpoints. A skipped cycle edge is dashed. The sorted cards record each edge’s weight and status; the component groups show which vertices are already connected. A check stage and its accept/reject stage are separate decisions. The counter counts candidate edges inspected, excluding sorting comparisons and internal DSU operations.

Change the preset or edit an edge weight. Invalid input preserves the current valid run. The player accepts 1–8 uniquely labelled vertices, up to 28 edges without self-loops or duplicate unordered pairs, and integer weights from −99 to 99. Zero is an edge weight, not absence. Shared controls provide stepping, seeking, speed, fullscreen, a link to a paused clean player and silent video export.

Algorithm cost and saved history

With an O(E log(E+1)) comparison sort, sorting costs O(E log(E+1)); DSU initialization costs O(V), and all finds and merges together cost O(E α(V)) amortized, with union by size and path compression. Here α is the very slowly growing inverse Ackermann function. Working memory is O(V+E) for DSU and the copied edge order, apart from the input. Early stopping does not remove the initial sorting cost.

The visualization additionally stores O(E+1) immutable snapshots of groups and accepted/rejected edges: O((E+1)(V+E)) history memory. It derives display groups from parent trees without changing the DSU, adding up to O((E+1)V log(V+1)) work, plus snapshot copies. These presentation costs are separate from the algorithm’s bound. Animation duration illustrates choices and is not a computation benchmark.

JavaScript implementation

This function returns original edge indices, total weight and final component count without animation history. It uses the same tie order, DSU and early stop as the player. Vertices are numbered 0 to n−1. It validates safe integer weights and their absolute sum to prevent overflow; it does not mutate the input edge list.

function kruskal(n, edges) {
    if (!Number.isInteger(n) || n < 1 || !Array.isArray(edges))
        throw new RangeError("Invalid graph");
    let budget = 0;
    const pairs = new Set();
    for (const e of edges) {
        if (!e || !Number.isInteger(e.from) || !Number.isInteger(e.to) ||
            e.from < 0 || e.from >= n || e.to < 0 || e.to >= n ||
            e.from === e.to || !Number.isSafeInteger(e.weight))
            throw new RangeError("Invalid edge");
        const key = [e.from, e.to].sort((a, b) => a - b).join(":");
        if (pairs.has(key)) throw new RangeError("Duplicate edge");
        pairs.add(key);
        budget += Math.abs(e.weight);
        if (!Number.isSafeInteger(budget)) throw new RangeError("Unsafe sum");
    }
    const order = edges.map((_, id) => id)
        .sort((a, b) => edges[a].weight - edges[b].weight || a - b);
    const parent = Array.from({ length: n }, (_, i) => i);
    const size = Array(n).fill(1);
    function find(v) {
        while (v !== parent[v]) {
            parent[v] = parent[parent[v]];
            v = parent[v];
        }
        return v;
    }
    const selected = [];
    let weight = 0, components = n;
    for (const id of order) {
        if (components === 1) break;
        const e = edges[id];
        let a = find(e.from), b = find(e.to);
        if (a === b) continue;
        if (size[a] < size[b]) [a, b] = [b, a];
        parent[b] = a;
        size[a] += size[b];
        selected.push(id);
        weight += e.weight;
        components--;
    }
    return { edges: selected, weight, components };
}