Exercise 1690Combinatorics › Graph theoryL1Added 3 Nov 2026

Kruskal's algorithm

#Kruskal#MST#greedy

Statement

Describe Kruskal's algorithm for finding a minimum spanning tree (MST).

Hint

Sort edges by weight; add in increasing order if they don't create a cycle.

Show solutionHide solution

Solution

Algorithm.
1. Sort all edges by increasing weight.
2. Initialize $T=\emptyset$ .
3. For each edge in order: add to $T$ if it does not create a cycle (union-find). Otherwise skip.

Correctness (sketch). Greedy exchange argument: any MST can be transformed to include the first edge chosen, without increasing weight.

Complexity. $O(|E|\log|E|)$ using union-find.

Conclusion. Kruskal gives a minimum spanning tree.

Kruskal's algorithm

Statement

Solution

More problems in Graph theory