All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class structure.UnionFind 

java.lang.Object
    |
    +----structure.UnionFind
public class UnionFind
extends Object
An implementation of a union-find structure. The universe consists of a number of values between 0 and n-1 These elements, initially, are all in their own set, labeled 0..n-1 respectively. Sets may be unioned. The resulting set takes on the identity of one of the two originals. In addition, the elements may be found in a set --- the result is the integer-label of the set containing the element.

Constructor Index

o UnionFind(int)
Construct a union-find set with elementCount elements.

Method Index

o find(int)
Find the number of the set containing the desired element.
o toString()
Construct a string representation of the union-find universe.
o union(int, int)
Merge sets containing elements i and j.

Constructors

o UnionFind 
public UnionFind(int elementCount)
Construct a union-find set with elementCount elements.

Precondition:
elementCount >= 0
Postcondition:
constructs elementCount disjoint sets labeled 0..elementCount-1

Parameters:
elementCount - The number of elements in the universe.

Methods

o find 
public int find(int i)
Find the number of the set containing the desired element.

Precondition:
0 <= i < elementCount
Postcondition:
returns the index or name of the set containing i

Parameters:
i - The element index.
Returns:
The index of the set.
o union 
public int union(int i,
                 int j)
Merge sets containing elements i and j. The identity of the ultimate set is the identity of one of the (possibly) two sets that contained i and j.

Precondition:
0 <= i,j < elementCount
Postcondition:
merges sets containing i and j, and returns new set name.

Parameters:
i - An element identifying one set.
j - An element identifying another set.
Returns:
The index of the set that is the union of the two sets containing i and j.
o toString 
public String toString()
Construct a string representation of the union-find universe.

Postcondition:
returns string representation of sets

Returns:
A string representing the sets in the union-find structure.
Overrides:
toString in class Object
All Packages  Class Hierarchy  This Package  Previous  Next  Index