Kruskal & Union Find

Go to:
> Material
> Lecture Recap

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations

Lecture Recap

This week we concluded our discussion on Minimum Spanning Trees with Kruskal’s Algorithm and the Union-Find data structure. This is also the algorithm I would recommend you to code up if it comes up in the exam (you can find a Java implementation of the Union-Find in the slides).

Kruskal’s Algorithm

Kruskal sorts all edges by weight and greedily adds them to the MST, skipping only those that would create a cycle.

• Strategy: Iterate through sorted edges. If an edge connects two disjoint components, add it.
• Bottleneck: Naively checking for cycles via DFS is too slow, requiring us to come up with a better data structure.

Union-Find Data Structure

To speed up Kruskal’s, we use Union-Find to manage connected components.

• Weighted Union: By always merging the smaller component into the larger one, we guarantee that any single element’s representative changes at most $\log |V|$ times.
• Runtime: This optimization reduces the total algorithm runtime to $O((|V|+|E|) \log |V|)$.