Interface UnionFinder

public interface UnionFinder

Specifies the methods necessary for a solution to the dynamic connectivity problem (without the possiblity of removal of connections). The interface assumes a graph of initially completely disconnected nodes which may be successively conected.

The pricipal purpose of such a class is to determine if any two nodes are connected either directly or indirectly through connections. to intermediate nodes.

The method union(a,b) directly connects two nodes, but any two nodes are said to be connected if a series of direct connections exist. For example, if node a is connected to node b directly and node b is directly connected to node c, then node a is connected to node c indirectly .

The find(a,b) method determines nodes a and be are connected either directly or indirectly. For the mathematically inclined, we say that find(a,b) is a kind of equivalance relation with the properties that

1. find(a,b) is equivalent to find(b,a) (Symmetry)
2. find(a,a) returns true (Reflexifity)
3. If find(a,b) and find(b,c) both return true, then find(a,c) also returns true. (Transitivity)

Method Summary

Modifier and Type	Method	Description
boolean	find(int a, int b)	Determines if a connection between node a and node b exists.
void	union(int a, int b)	Connects two given nodes.

Method Details

union

void union(int a,
 int b)

Connects two given nodes. Importantly, this method should first checked if the two nodes are already connected by calling find(a,b). In the case that they are already connected, nothing further should be done.

Parameters:

a - the first node to be connected.

b - the second node to be connected.

find

boolean find(int a,
 int b)

Determines if a connection between node a and node b exists.

Parameters:

a - the first node to be checked.

b - the second node to be checked.

Returns:

true if a and b are connected by some path (directly or indirectly).