Java Reference
In-Depth Information
R
W
A
B
X
Y
Z
C
D
E
F
PARENT'S INDEX
0
0
1
1
1
2
7
7
7
LABEL
R
A
B
C
D
E
F
W
X
Y
Z
NODE INDEX
0
1
2
3
4
5
6
7
8
9
10
Figure6.5
The parent pointer array implementation. Each node corresponds
to a position in the node array, which stores its value and a pointer to its parent.
The parent pointers are represented by the position in the array of the parent. The
root of any tree stores
ROOT
, represented graphically by a slash in the “Parent's
Index” box. This figure shows two trees stored in the same parent pointer array,
one rooted at R, and the other rooted at W.
I
A
B
D
F
J
C
H
E
G
Figure6.6
A graph with two connected components.
reflexive, symmetric, and transitive. Thus, if objects A and B are equivalent, and
objects B and C are equivalent, we must be able to recognize that objects A and C
are also equivalent.
There are many practical uses for disjoint sets and representing equivalences.
For example, consider Figure 6.6 which shows a graph of ten nodes labeled A
through J. Notice that for nodes A through I, there is some series of edges that
connects any pair of the nodes, but node J is disconnected from the rest of the
nodes. Such a graph might be used to represent connections such as wires be-
tween components on a circuit board, or roads between cities. We can consider
two nodes of the graph to be equivalent if there is a path between them. Thus,
nodes A, H, and E would be equivalent in Figure 6.6, but J is not equivalent to any
other. A subset of equivalent (connected) edges in a graph is called a connected
component. The goal is to quickly classify the objects into disjoint sets that corre-
