Graph algorithms / interactive lesson

Kruskal's Minimum Spanning Tree

Sort every edge globally, then greedily accept the cheapest one that does not form a cycle. Watch the Union-Find structure merge components one step at a time and connect the cut property to a clean implementation.

University Guided lesson

Snapshot 1/14

Weighted undirected graph · orange = candidate · green = MST · red = rejected

Decision timeline

Sort all 9 edges by weight

initialize / current step

Sort all 9 edges by weight

Kruskal's algorithm starts by sorting every edge in the graph. Each node begins as its own isolated component — there are no connections yet. We will sweep through the sorted list and greedily accept or reject each edge.

MST edges

rejected

weight

Sorted edges

All edges ordered by weight. Algorithm sweeps top-to-bottom.

1B – C1

2A – C2

3D – E2

4E – F3

5A – B4

6B – D5

7D – F6

8C – D8

9C – E10

Components

Each group shows nodes that are currently connected.

Why this works

Unlike Prim's algorithm, which grows a single tree outward from one node, Kruskal works globally: it inspects every edge in the graph before making any decision, then merges components one edge at a time.

Complexity

Sorting edges takes O(E log E). Each union-find operation runs in O(α(V)) amortised — where α is the inverse Ackermann function, effectively constant. Total: O(E log E).

About the algorithm

Kruskal's algorithm constructs a minimum spanning tree by sorting all edges globally and greedily accepting the cheapest one that does not form a cycle. A Union-Find structure detects cycles in near-constant time, making the algorithm particularly efficient on sparse graphs.

History

Joseph Kruskal published the algorithm in 1956. He described it as an extremely natural approach: simply sort all edges and add each one as long as it does not complete a cycle. The same idea was independently noted by Loberman and Weinberger, and is closely related to work by Borůvka in 1926.

How it works

Sort every edge by weight. Maintain a Union-Find (disjoint-set) structure that tracks which nodes are already connected. For each edge in order: if its two endpoints belong to different components, accept it and merge those components; otherwise reject it to avoid a cycle. Stop when V – 1 edges have been accepted.

When to use it

Kruskal excels when the graph is sparse (E ≪ V²) because it sorts edges rather than scanning the full adjacency matrix. It naturally discovers multiple MST components in parallel, making it straightforward to extend to disconnected graphs (minimum spanning forest).

Code companion

Connect each visual decision to an implementation pattern.

edges = sort all edges by weight
uf = UnionFind(all nodes)
tree = []

for edge in edges:
  if not uf.connected(edge.u, edge.v):
    tree.add(edge)
    uf.union(edge.u, edge.v)
  if tree.size == V - 1:
    break

return tree