Minimum Spanning Trees: Kruskal's Algorithm — Visualized in 7 Minutes

How do you connect every vertex of a weighted graph as cheaply as possible? Kruskal's algorithm (1956) does it with one greedy rule: take the edges from cheapest to most expensive, and skip any edge that would close a cycle. We run it step by step, prove why the greedy choice is never a mistake, and see how Union–Find makes the cycle check instant. In this video, we visualize: • Spanning trees: n − 1 edges that reach every vertex without forming a cycle • The minimum spanning tree problem, and two spanning trees of the same graph (weights 48 and 64) • Kruskal's algorithm, line by line, run on an 8-vertex graph — 7 edges added, 4 skipped, components shown as colours • Why it works: the cut property, and the exchange argument (drop a 9, keep a 7) carried out on the same graph • Union–Find: Find and Union replace the search for a cycle • The running time O(m log m): the sort dominates, and the Union–Find part is essentially linear This is an updated remake of our earlier Kruskal video, now with English narration and a proof of correctness. Animated with Manim. Chapters: 0:00 Spanning trees 0:34 The minimum spanning tree problem 1:17 Kruskal's algorithm 3:52 Why does it work? The cut property 5:32 Union–Find 6:28 Running time 6:54 Outro Follow us on X: https://x.com/graphgarden01 #GraphTheory #Mathematics #Algorithms #KruskalsAlgorithm #MinimumSpanningTree #ComputerScience