Blog

Union-Find and Minimum Spanning Trees: Building Networks with Kruskal

With path compression and union by rank, Union-Find answers "are these two elements in the same group?" in practically constant time; the naive version is 4,300 times slower on a long chain. We write a DisjointSet in C#, merge duplicate customer accounts through shared e-mails and phones, build the cheapest fiber network between offices with Kruskal, and confirm the result with Prim.