Kruskal's MST

How Kruskal's algorithm works

Three steps:

1. Sort all edges by weight ascending. O(E log E).
2. Initialize a union-find structure with one component per vertex. O(V).
3. Iterate through sorted edges. For each edge (u, v, w): if u and v are in different components (find(u) ≠ find(v)), add the edge to the MST and union the components. O(E α(V)).

Stop when V-1 edges have been added (forms a spanning tree) or when all edges are processed (graph may be disconnected). Total time — O(E log E), dominated by the sort.

Walk-through example

Graph with 6 vertices, 9 edges:

Edges sorted by weight:
  (A, B, 1)   take — A and B in different components → union
  (D, F, 2)   take — D and F different → union
  (B, C, 3)   take — B's component {A,B} different from C's {C} → union
  (D, E, 4)   take — D's component {D,F} different from E's {E} → union
  (E, F, 5)   skip — E and F now in same component (would create cycle)
  (B, F, 6)   take — {A,B,C} different from {D,E,F} → union
              MST has 5 edges (= V - 1) — done.
  (remaining edges skipped — no longer needed)

MST total weight: 1 + 2 + 3 + 4 + 6 = 16

The algorithm took 5 edges (V-1 for V=6), skipping any edge that would create a cycle. Union-find made cycle checks trivial — find(u) and find(v) compared in O(α) per check.

Kruskal vs Prim

	Kruskal	Prim
Approach	Sort edges, take lightest non-cycling	Grow tree from start vertex, take lightest extending edge
Data structure	Sorted edge list + union-find	Min-priority queue (heap)
Time (sparse, E ≈ V)	O(V log V)	O((V + E) log V)
Time (dense, E ≈ V²)	O(V² log V)	O(V²) with adj matrix
Code complexity	~30 lines + union-find	~25 lines + heap
Disconnected graphs	Produces minimum spanning forest naturally	Only sees one component
Best for	Sparse graphs, simple implementation	Dense graphs, when you have a heap library

For most real graphs (sparse), Kruskal and Prim are competitive. Pick whichever your team is more comfortable with; they produce equivalent results.

JavaScript implementation

// Requires the UnionFind class from the union-find article
function kruskalMST(n, edges) {
  // edges: [[u, v, weight], ...] where u, v are 0..n-1
  edges.sort((a, b) => a[2] - b[2]);

  const uf = new UnionFind(n);
  const mst = [];
  let totalWeight = 0;

  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {  // returns true iff actually merged (no cycle)
      mst.push([u, v, w]);
      totalWeight += w;
      if (mst.length === n - 1) break; // tree complete
    }
  }

  return { mst, totalWeight, isSpanningTree: mst.length === n - 1 };
}

// Usage
const edges = [
  [0, 1, 1], [0, 5, 6], [1, 2, 3],
  [3, 4, 4], [3, 5, 2], [4, 5, 5],
];
const { mst, totalWeight, isSpanningTree } = kruskalMST(6, edges);
console.log('MST weight:', totalWeight);  // 16
console.log('Spanning tree?', isSpanningTree);  // true

Python implementation

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        root = x
        while self.parent[root] != root: root = self.parent[root]
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]: self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]: self.parent[ry] = rx
        else: self.parent[ry] = rx; self.rank[rx] += 1
        return True

def kruskal_mst(n, edges):
    edges = sorted(edges, key=lambda e: e[2])
    uf = UnionFind(n)
    mst = []
    total = 0
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1: break
    return mst, total

When to use Kruskal's

• Network design. Find the cheapest set of cables to connect every office. Edges are possible cables; weights are installation costs. MST gives the minimum-cost connection.
• Clustering and segmentation. Hierarchical clustering — sort edges by similarity, merge clusters until you have k components. Image segmentation (Felzenszwalb-Huttenlocher) does this with pixel-similarity edges.
• Approximation algorithms for the traveling salesman problem. Christofides' algorithm uses MST as a building block — its cost is at most 1.5× the optimal TSP tour for metric instances.
• Critical-path analysis in networks. Failure of the heaviest edge in the MST disconnects the network minimally.
• Building blocks for harder problems. Many algorithms reduce to MST — Borůvka's, Steiner trees, partial spanning trees.

Common bugs and pitfalls

• Forgetting to stop after V-1 edges. Continuing past V-1 doesn't change the MST (subsequent edges all create cycles), but wastes work. Cheap optimization.
• Not using union-find for cycle detection. Naive cycle detection (DFS each time) is O(V) per edge, total O(V·E) — much slower than union-find's O(α(V)) per edge.
• Failing on graphs with parallel edges. Multiple edges between the same pair of vertices are fine — only the lightest gets accepted (others create cycles). But check that your edge representation doesn't lose information when sorting.
• Assuming the graph is connected. On a disconnected graph, Kruskal's produces a minimum spanning forest. Document or check whether the input is connected; report disconnection by checking the final edge count.
• Using Kruskal's when you need a Steiner tree. MST connects all vertices. Steiner tree connects a SUBSET of vertices, possibly using extra "Steiner points" not in the original set. NP-hard in general; Kruskal's is the wrong tool.