Java Reference
In-Depth Information
the vertices. In general, you use either a list or a dictionary to hold the vertices, and an array or a list
to represent the edges. Each representation of the edges has its own advantages, but the list
representation is most typical.
Two common implementations of the ADT graph use either an array or a list to represent the
graph's edges. The array is typically a two-dimensional array called an
adjacency matrix
. The list
is called an
adjacency list
. Each of these constructs represents the connections—that is, the
edges—among the vertices in the graph.
29.1
The adjacency matrix for a graph of
n
vertices has
n
rows and
n
columns. Each row and each col-
umn corresponds to a vertex in the graph. You number the vertices from 0 through
n
-
1 to match
the row indices and the column indices. If
a
ij
is the element in row
i
and column
j
of the matrix,
a
ij
indicates whether an edge exists between vertex
i
and vertex
j
. For an unweighted graph, you can
use boolean values in the matrix. For a weighted graph, you can use edge weights when edges exist
and a representation of infinity otherwise.
Figure 29-1 provides an example of an unweighted, directed graph and its adjacency matrix.
Let's consider vertex
A
of the graph, which we have numbered as vertex 0. Since directed edges
exist from vertex
A
to each of the vertices
B
,
D
, and
E
, the matrix elements
a
01
,
a
03
, and
a
04
are
true. We have used a “T” in the figure to represent true. The other entries in the first row are false
(blank in the figure).
Although a directed edge exists from vertex
A
to vertex
B
, the converse is not true. Therefore,
a
10
is false, even though
a
01
is true. The adjacency matrix for an undirected graph, however, is
symmetric
; that is,
a
ij
and
a
ji
have the same value. When an undirected graph has an edge from
vertex
i
to vertex
j
, it also has an edge from vertex
j
to vertex
i
.
VideoNote
The adjacency matrix
FIGURE 29-1
(a) An unweighted, directed graph and (b) its adjacency matrix
(a)
(b)
0
3
6
A
B
C
D
EFG
H
I
A
D
G
A
B
C
T
T
0
1
2
3
4
5
T
T
T
4
D
T
1
B
E
H
7
T
T
T
T
E
F
G
H
I
T
6
7
8
C
F
I
T
2
5
8
T
012
34 5 6
8
7
