Motivation
Lesson 2 of 9 in Coddy's Kruskal's Algorithm - Graph Algorithms course.
Kruskal keeps the growing forest of chosen edges in a union-find structure. To add an edge safely, it checks whether the two endpoints are already in the same set (that would make a cycle).
Why learn Kruskal?
- Real MSTs: network design, clustering, and laying cable or roads at minimum cost.
- Union-find: a beautiful, reusable structure for tracking connectivity that shows up all over computer science.
- Greedy correctness: another example where always taking the cheapest safe option yields the global optimum.
All minimum spanning trees of a graph use the same multiset of edge weights, so the total weight (and the largest edge) is unique.
Try it yourself
This lesson doesn't include a code challenge.
Test yourselfThis lesson includes a short quiz. Start the lesson to answer it and track your progress.
