Minimum Spanning Tree

Kruskal's Algorithm

Sort all edges by weight. Process them smallest first: add an edge if it connects two previously disconnected components (check with union-find). Skip it if it would create a cycle. Stop after V−1 edges.

O(E log E)

O(V)

How It Works

Kruskal's algorithm builds a minimum spanning tree by considering edges globally, cheapest first. Sort all edges by weight, then scan them in order: add an edge if its endpoints lie in different components (checked with union-find), skip it if they are already connected, since adding it would create a cycle. Stop once V−1 edges have been accepted. The cut property justifies the greed: the lightest edge crossing any partition of the vertices is always safe to include in some MST.

Sorting dominates the cost at O(E log E), while the union-find operations are nearly O(1) amortized with path compression and union by rank. Kruskal's shines on sparse graphs and edge-list inputs, and it naturally handles disconnected graphs by producing a minimum spanning forest instead of failing.

Step-by-Step Visualization

Kruskal's MST: sort edges by weight

Edges sortedweight: 1, 2, 4, 7, 8

1/3

Code

Java

static int kruskal(int[][] edges, int n) {
  Arrays.sort(edges, (a, b) -> a[2] - b[2]);
  UnionFind uf = new UnionFind(n);
  int mstWeight = 0, edgeCount = 0;

  for (int[] e : edges) {
    if (uf.find(e[0]) != uf.find(e[1])) {
      uf.union(e[0], e[1]);
      mstWeight += e[2];
      if (++edgeCount == n - 1) break;
    }
  }
  return mstWeight;
}

Tips & Gotchas

1Sort all edges by weight

2Process smallest first: add edge if it doesn't create a cycle

3Use Union-Find for efficient cycle detection

Practice Problems

1Min Cost to Connect All Points
2Connecting Cities With Minimum Cost
3Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

About the Minimum Spanning Tree Pattern

Connect all nodes in an undirected weighted graph with minimum total edge weight, using exactly V−1 edges (no cycles). Two classic algorithms: sort edges and add greedily (Kruskal's), or grow a tree from a node (Prim's).

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

Kruskal's or Prim's — how do I decide?

Kruskal's works directly on an edge list and is a natural fit for sparse graphs or problems that hand you edges up front; Prim's with a heap suits adjacency-list graphs and dense inputs. In interviews Kruskal's is often quicker to write if you already have a union-find implementation ready.

Why does skipping cycle-forming edges never lose the optimal answer?

If both endpoints of an edge are already connected, the tree contains a path between them made entirely of edges no heavier than the current one, since edges arrive in sorted order. Swapping the new edge in could only match or worsen the total weight, so discarding it is safe.