Algorithms

Union-Find

Track connected components in O(α(n)) ≈ O(1).

In plain terms

Galler & Fischer, 1964; Tarjan's analysis 1975. Path compression + union-by-rank. Powers Kruskal MST and equivalence-class problems.

Origin

Bernard Galler and Michael Fischer, 1964. Robert Tarjan analysed the inverse-Ackermann time bound in 1975. The "almost-O(1)" data structure.

Where it shows up in production

Kruskal's MST Union-find decides whether two vertices are already connected. The whole algorithm hinges on it.
Image segmentation Connected components in images via union-find on pixel neighbourhoods.
Network connectivity Real-time queries — "are these two nodes in the same partition?" — in O(α(n)).

On Semicolony

Sources & further reading

Found this useful?