Kruskal's Algorithm

Graph Theory · Axiom Academy

Building Minimum Spanning Trees Edge by Edge A minimum spanning tree (MST) connects all vertices in a graph with minimum total edge weight. Kruskal's algorithm builds the MST by considering edges in order from smallest to largest weight. The key insight: start with a forest of isolated vertices, then merge trees by adding edges, always choosing the cheapest edge that connects two different trees. The first step of Kruskal's algorithm is to sort all edges in non-decreasing order by weight. This allows us to greedily select the cheapest edges first. For a graph with E edges, this sorting step takes O(E log E) time and dominates the algorithm's complexity. 3. Union-Find for Cycle Detection To detect whether adding an edge would create a cycle, Kruskal's uses the Union-Find (Disjoint Set) data structure. Each vertex starts in its own set. When we add an edge (u, v), we check if u and v are in the same set. If not, we union their sets. If they're already in the same set, the edge would create a cycle. 4. Complete Algorithm Walkthrough Watch as Kruskal's algorithm processes edges in order, building the MST step by step: Start with all vertices as separate trees (forest) Consider the next cheapest edge (u, v) If u and v are in different trees, add the edge and merge the trees If u and v are in the same tree, skip the edge (would create cycle) Repeat until we have n-1 edges (where n is the number of vertices) 5. Kruskal's vs. Prim's Algorithm

This is the written version of the interactive lesson above. See the full Graph Theory course.