Sunday, January 19, 2014

Union Find

The Union-Find data structure is used to keep track of a partition of a set and supports two operations. The Union(x, y) operation merges the subsets containing x and y, and the Find(x) operation returns the name of the leader element of the subset to which x belongs.

The implementation is based on a response to this post on StackOverflow, but extended with a makeSet operation, a getNumGroups operation, and tests.

Union-Find can be used to create very efficient implementations of Kruskal’s minimum spanning tree algorithm and the single-link hierarchical agglomerative clustering algorithm.



Post a Comment