Kruskal's Algorithm Visualizer

Kruskal's algorithm is greedy in the most literal way possible: sort every edge by weight, then take them one at a time from cheapest to most expensive, skipping any that would create a cycle. That is the entire algorithm. Whether it works comes down to a single question — how do you decide, quickly, whether adding an edge closes a cycle?

The answer is union-find, a data structure so efficient its complexity is expressed with the inverse Ackermann function, which is less than 5 for any input that could physically exist. Learning Kruskal is mostly an excuse to learn union-find, and union-find is worth learning on its own terms.

What is Kruskal's algorithm?

Kruskal's algorithm finds a minimum spanning tree by considering edges in order of increasing weight and adding each one if — and only if — its two endpoints are not already connected. After V−1 edges have been accepted, every vertex is connected and the tree is complete.

The structural contrast with Prim's algorithm is worth holding on to. Prim grows one connected blob outward from a start vertex. Kruskal maintains a forest of fragments scattered across the graph, which merge as cheap edges connect them, and only becomes a single tree at the very end.

That difference has a practical consequence: Kruskal needs no adjacency structure at all. It works from a bare list of edges, which is often exactly how graph data arrives from a file or a database. Prim requires a way to enumerate the neighbours of a vertex.

Why it works

Correctness rests on the same cut property that justifies Prim's algorithm: for any partition of the vertices into two non-empty sets, the cheapest edge crossing between them belongs to some minimum spanning tree.

When Kruskal accepts an edge, its two endpoints are in different components. Take the cut separating one endpoint's component from everything else. Every edge crossing that cut has weight at least as large as the current one — otherwise it would have been considered earlier and, since its endpoints were also in different components at that point, it would have been accepted. So the accepted edge is a cheapest crossing edge, and by the cut property it is safe.

When Kruskal rejects an edge, both endpoints are already in the same component, so a path between them already exists. Adding the edge would create a cycle, and by the cycle property — the heaviest edge on any cycle is not in the MST, provided weights are distinct — this edge is never needed.

Each accepted edge reduces the number of components by exactly one. Starting from V components, V−1 accepted edges leave exactly one: a spanning tree.

Union-find, the structure that makes it work

Union-find — also called a disjoint-set union, or DSU — tracks a partition of elements into non-overlapping sets and supports two operations: find, which returns a canonical representative for an element's set, and union, which merges two sets. Two elements are in the same set exactly when their finds return the same representative.

The naive version stores a parent pointer per element and walks up to the root on every find. Without care, the trees degenerate into linked lists and find becomes O(n). Two optimisations fix this, and both are short.

Path compression: during a find, repoint every node visited directly at the root. The next find on any of them is immediate. This is three extra lines and does most of the work.

Union by rank or size: when merging, attach the smaller tree under the larger one, so the depth grows as slowly as possible. Combined with path compression, the amortised cost per operation becomes O(α(n)), where α is the inverse Ackermann function — under 5 for any n up to the number of atoms in the observable universe. It is constant time in every sense that matters.

Step-by-step walkthrough

A graph with edges B–C at 1, A–B at 2, A–C at 3, B–D at 4, C–D at 5. Four vertices, so the MST needs three edges.

1. Sort the edges: B–C (1), A–B (2), A–C (3), B–D (4), C–D (5).
2. B–C at 1: B and C are in different components. Accept. Components: {A}, {B, C}, {D}.
3. A–B at 2: A and B are in different components. Accept. Components: {A, B, C}, {D}.
4. A–C at 3: find(A) and find(C) return the same representative — both are in the merged component. Reject, it would close a cycle.
5. B–D at 4: different components. Accept. Components: {A, B, C, D}. Three edges accepted, so stop; C–D is never examined.
6. Total weight 1 + 2 + 4 = 7 — the same total Prim's algorithm produces on this graph, as it must.

How the animation above works

The edge list is sorted before anything happens, and each edge is then considered in turn — accepted edges turn mint, rejected ones are explicitly flagged. Rejections are the interesting frames: those are the edges whose endpoints union-find has determined are already connected.

Compare the shape against Prim's algorithm on the same graph. Kruskal's mint edges appear scattered across the canvas as isolated fragments, sometimes far from each other, and only merge into a single connected structure near the end. Prim's grow as one expanding blob. Both finish with the same total weight, which is a good demonstration that a greedy algorithm's *construction order* and its *result* are separate things.

Notice too that Kruskal often stops before examining every edge — once V−1 edges are accepted the remaining ones cannot matter, so the most expensive edges in the graph are frequently never looked at.

Time and space complexity

O(E log E) overall, dominated entirely by sorting the edges. The union-find operations contribute O(E·α(V)), which is effectively O(E) — negligible against the sort.

Since E is at most V², log E is at most 2 log V, so the complexity is often written O(E log V). The two forms are equivalent up to a constant factor.

If the edges are already sorted, or the weights are small integers that can be sorted in linear time with counting or radix sort, the whole algorithm drops to near O(E·α(V)), which is essentially linear. This is a real optimisation and easy to miss.

O(V) space for the union-find structure, plus O(E) if the edge list must be copied to sort it in place.

Kruskal or Prim?

Kruskal wins on sparse graphs, where E is much smaller than V². Sorting a small edge list is cheap, and union-find operations are effectively free.

Prim wins on dense graphs, where its O(V²) adjacency-matrix implementation avoids sorting a near-V² edge list entirely.

Kruskal wins when the input is an edge list, which is how graph data usually arrives from files, databases and CSV exports — no adjacency structure needs building.

Kruskal handles disconnected graphs naturally. It simply produces a minimum spanning forest, one tree per component, with no special handling. Prim's algorithm silently spans only the start vertex's component and needs an outer loop to cover the rest.

Prim wins when the graph is discovered incrementally, because Kruskal must see and sort all edges before it can begin.

For very large graphs, Borůvka's algorithm deserves a mention: it adds the cheapest edge out of every component simultaneously, halving the component count each round. It is the oldest MST algorithm — 1926, for electrifying Moravia — and it parallelises far better than either Prim or Kruskal, which is why it underlies most distributed MST implementations.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Kruskal's Algorithm in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Union-find with path compression and union by size.
 * Amortised O(alpha(n)) per operation — effectively constant.
 */
class DisjointSet {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.size = new Array(size).fill(1);
  }

  find(x) {
    // Path halving: points each node at its grandparent as we walk up.
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }

  /** Returns false if a and b were already connected. */
  union(a, b) {
    let rootA = this.find(a);
    let rootB = this.find(b);
    if (rootA === rootB) return false;

    // Attach the smaller tree under the larger one to keep depth low.
    if (this.size[rootA] < this.size[rootB]) [rootA, rootB] = [rootB, rootA];
    this.parent[rootB] = rootA;
    this.size[rootA] += this.size[rootB];
    return true;
  }
}

function kruskal(vertexCount, edges) {
  const sorted = [...edges].sort((a, b) => a.weight - b.weight);
  const dsu = new DisjointSet(vertexCount);
  const mst = [];
  let totalWeight = 0;

  for (const edge of sorted) {
    // union() returns false when the endpoints are already connected,
    // which is exactly the cycle check.
    if (dsu.union(edge.from, edge.to)) {
      mst.push(edge);
      totalWeight += edge.weight;
      if (mst.length === vertexCount - 1) break; // done; skip the rest
    }
  }

  return { mst, totalWeight };
}

const edges = [
  { from: 1, to: 2, weight: 1 },
  { from: 0, to: 1, weight: 2 },
  { from: 0, to: 2, weight: 3 },
  { from: 1, to: 3, weight: 4 },
  { from: 2, to: 3, weight: 5 },
];

console.log(kruskal(4, edges)); // totalWeight 7

Advantages and disadvantages

Real-world applications

• Network design where the input is a list of possible links with costs — cabling, road planning, pipeline layout.
• Single-linkage clustering: run Kruskal and stop once k components remain, which gives k clusters directly with no distance threshold to tune.
• Image segmentation, where pixels or superpixels form a graph weighted by colour difference.
• Approximation algorithms for the travelling salesman problem, using the MST as the basis for a bounded-error tour.
• Circuit design and VLSI routing, minimising total wire length.
• Detecting redundant connections in a network — every rejected edge is one that could be removed without disconnecting anything.
• Union-find on its own, for dynamic connectivity queries, Kruskal-based percolation models and equivalence-class problems.

Interview questions

The questions that actually get asked about Kruskal's Algorithm, with the answers an interviewer is listening for.

1. Q1. How does Kruskal's algorithm detect cycles efficiently?

   With union-find. Each vertex starts in its own set; accepting an edge unions the sets of its endpoints. An edge whose endpoints are already in the same set would close a cycle, and find detects that in effectively constant time. The alternative — running a DFS or BFS to check connectivity before each edge — would cost O(V + E) per edge and make the whole algorithm O(E·V), worse than the sort it was trying to be cheaper than.

2. Q2. What is the time complexity of union-find, and why is it that?

   O(α(n)) amortised per operation with both path compression and union by rank, where α is the inverse Ackermann function — under 5 for any n up to about 2^65536. Path compression flattens the tree during every find; union by rank keeps the tree shallow by attaching the smaller side under the larger. Either optimisation alone gives O(log n); together they give the near-constant bound.

3. Q3. When would you choose Kruskal over Prim?

   On sparse graphs, where sorting a small edge list is cheap and Prim's heap overhead is not repaid. When the input is already an edge list rather than an adjacency structure. When the graph may be disconnected and you want a spanning forest without special handling. And when the edges are already sorted or have small integer weights, which drops Kruskal to nearly linear time.

4. Q4. Why is it safe to reject an edge whose endpoints are already connected?

   By the cycle property: on any cycle, the heaviest edge is not needed in the MST when weights are distinct. If both endpoints are already connected, a path between them exists, and every edge on that path was accepted earlier — meaning each was no heavier than the edge being considered. So the current edge is the heaviest on the cycle it would create, and excluding it is safe.

5. Q5. How would you use Kruskal to cluster data into k groups?

   Build a graph where the vertices are data points and the edge weights are distances, then run Kruskal but stop once V−k edges have been accepted rather than V−1. The remaining k components are the clusters. This is exactly single-linkage hierarchical clustering, and it needs no distance threshold — only the desired number of clusters.

Common mistakes

• Implementing union-find without path compression or union by rank, which degrades find to O(V) and makes the algorithm slower than sorting.
• Comparing parent[u] === parent[v] rather than find(u) === find(v), which only checks immediate parents and misses most cycles.
• Forgetting to sort the edges at all, which produces a spanning tree that is valid but not minimum.
• Continuing to iterate after V−1 edges have been accepted rather than breaking, which wastes time on edges that cannot be used.
• Assuming the graph is connected and reporting a tree when the result is actually a forest of several components.
• Sorting the caller's edge array in place, which mutates their data as a side effect.
• Mixing up union by rank and union by size — either works, but tracking one and comparing the other silently breaks the depth guarantee.

Optimisation tips

• Always use both path compression and union by rank or size; each is a few lines and together they are the difference between O(α) and O(log n).
• Break as soon as V−1 edges have been accepted — on dense graphs this skips most of the edge list.
• If weights are small integers, sort with counting or radix sort to drop the dominant term and make the algorithm nearly linear.
• Path halving (parent[x] = parent[parent[x]] inside the loop) is simpler than recursive path compression, avoids recursion depth issues, and performs just as well.
• Filter obviously useless edges before sorting — self-loops, and duplicate edges beyond the cheapest between the same pair.
• For very large or distributed graphs, use Borůvka's algorithm, which adds the cheapest edge out of every component in parallel and halves the component count each round.

Summary

Kruskal's algorithm sorts every edge by weight and accepts them cheapest-first, skipping any whose endpoints are already connected. Its correctness follows from the cut property for accepted edges and the cycle property for rejected ones, and each acceptance reduces the component count by one until a single spanning tree remains.

The interesting part is not the greedy loop but the cycle check, which union-find answers in effectively constant time using path compression and union by rank. That reduces the whole algorithm to O(E log E), dominated by the sort — so it wins on sparse graphs and on edge-list inputs, while Prim's O(V²) form wins on dense ones. Kruskal also handles disconnected graphs for free, producing a minimum spanning forest where Prim would silently span only one component.

Frequently asked questions

Related algorithms

• Prim's Algorithm

  Grow a minimum spanning tree outward from one node, always taking the cheapest edge out.

  O(E log V)Advanced

• Dijkstra's Algorithm

  Greedily settle the nearest unvisited node to get shortest paths on non-negative weights.

  O((V + E) log V)Advanced

• Depth-First Search

  Follow one branch as deep as it goes, then backtrack — a stack, or recursion.

  O(V + E)Intermediate