Package org.jgrapht.alg.util

Class UnionFind<T>

java.lang.Object
org.jgrapht.alg.util.UnionFind<T>
public class UnionFind<T> extends Object
An implementation of Union Find data structure. Union Find is a disjoint-set data structure. It supports two operations: finding the set a specific element is in, and merging two sets. The implementation uses union by rank and path compression to achieve an amortized cost of O(a(n)) per operation where a is the inverse Ackermann function. UnionFind uses the hashCode and equals method of the elements it operates on.
Since:
Feb 10, 2010
Author:
Tom Conerly

  • Constructor Details

    • UnionFind

      public UnionFind(Set<T> elements)
      Creates a UnionFind instance with all of the elements of elements in seperate sets.

  • Method Details

    • addElement

      public void addElement(T element)
      Adds a new element to the data structure in its own set.
      Parameters:
      element - The element to add.

    • getParentMap

      protected Map<T,T> getParentMap()
      Returns:
      map from element to parent element

    • getRankMap

      protected Map<T,Integer> getRankMap()
      Returns:
      map from element to rank

    • find

      public T find(T element)
      Returns the representative element of the set that element is in.
      Parameters:
      element - The element to find.
      Returns:
      The element representing the set the element is in.

    • union

      public void union(T element1, T element2)
      Merges the sets which contain element1 and element2.
      Parameters:
      element1 - The first element to union.
      element2 - The second element to union.