Advanced · Module 18 · Lesson 3 of 4

Kruskal's algorithm

A minimum spanning tree connects every vertex at the lowest total edge weight. Kruskal's algorithm sorts the edges and takes each one that joins two different components, with union-find deciding in nearly constant time.

ProAbout 14 minutes

By the end you can

Define a minimum spanning tree and recognize problems that ask for one
Run Kruskal's algorithm with sorting and union-find, and state its cost
Justify the greedy choice with the cut property

Builds on Union by rank and path compression, Exchange arguments.

01 · A question first

A utility company must lay cable between ten towns so that every town is connected, directly or through others, and each possible link has a price. The cheapest network has no loops, since a loop always contains a cable you could remove. But which links should it use? Taking the cheapest link that doesn't close a loop, over and over, turns out to be provably optimal.

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

Connecting everything as cheaply as possible
The algorithm
Why greedy is correct here
Cost
Ties and uniqueness
Variations
Kruskal on geometric problems
Pseudocode & Multi-Language Implementations (C++, Java, Python)

See plans Already a member? Sign in

03 · Practice

Practice · hard · LeetCodeFind critical and pseudo-critical edges in a minimum spanning treeClassify each edge as in every minimum spanning tree, in some, or in none, by rerunning Kruskal with the edge removed or forced in.Practice · medium · LeetCodeMin cost to connect all pointsConnect every point at the lowest total Manhattan distance, with the O(n²) array version of Prim's algorithm.

Asked in interviews

Why does Kruskal's greedy algorithm produce a minimum spanning tree?

Something wrong with this lesson? Report a problem