Pattern visualizer
Kruskal's Algorithm (MST)
A spanning tree only needs n - 1 edges to connect every vertex with no cycle, and among every possible spanning tree Kruskal finds the lightest one with a simple greedy rule: sort all edges by weight, then walk them lightest first, accepting an edge only when its two endpoints are not already connected. Disjoint set union answers 'already connected?' in near constant time — each vertex tracks which component it belongs to, shown below as a badge, and two vertices sharing a badge means any edge between them would only close a cycle, so it gets skipped. The highlighted edges are the ones accepted into the tree so far. Animated on: 4 vertices, weighted undirected edges (0-1)=1, (0-2)=4, (1-2)=2, (1-3)=6, (2-3)=3 — find the minimum spanning tree's total weight using Kruskal's algorithm..
Sort edges by weight, union-find to skip anything that closes a cycle
4 vertices, 5 weighted undirected edges
4 vertices and 5 weighted edges. The goal is not just any spanning tree but the one with the smallest total weight — Kruskal builds it by looking at edges lightest-first and taking any edge that does not close a cycle.
1FUNCTION kruskalMST(n, edges):2 SORT edges BY weight ASCENDING3 parent[i] <- i FOR EACH i FROM 0 TO n - 14 mstWeight <- 05 count <- 06 FOR EACH (u, v, w) IN edges7 IF FIND(u) != FIND(v)8 UNION(u, v)9 mstWeight <- mstWeight + w10 count <- count + 111 RETURN mstWeight
← / → step · space play · Home restart