Java Reference
In-Depth Information
14.1.1
representation
The first thing to consider is how to represent a graph internally. Assume that
the vertices are sequentially numbered starting from 0, as the graph shown in
Figure 14.1 suggests. One simple way to represent a graph is to use a
two-dimensional array called an
adjacency matrix
. For each edge (
v, w
), we
set
a[v][w]
equal to the edge cost; nonexistent edges can be initialized with a
logical
INFINITY
. The initialization of the graph seems to require that the entire
adjacency matrix be initialized to
INFINITY
. Then, as an edge is encountered,
an appropriate entry is set. In this scenario, the initialization takes time.
Although the quadratic initialization cost can be avoided (see Exercise 14.6),
the space cost is still , which is fine for dense graphs but completely
unacceptable for sparse graphs.
An
adjacency matrix
represents a graph
and uses quadratic
space.
OV
2
(
)
OV
2
(
)
For sparse graphs, a better solution is an
adjacency list,
which represents
a graph by using linear space. For each vertex, we keep a list of all adjacent
vertices. An adjacency list representation of the graph in Figure 14.1 using a
linked list is shown in Figure 14.2. Because each edge appears in a list node,
the number of list nodes equals the number of edges. Consequently,
space is used to store the list nodes. We have lists, so additional
space is also required. If we assume that every vertex is in some edge, the
number of edges is at least
An
adjacency list
represents a graph,
using linear space.
OE
()
V
OV
()
V
2
⁄
. Hence we may disregard any
OV
()
terms when an
()
OE
OE
term is present. Consequently, we say that the space
requirement is
()
, or linear in the size of the graph.
The adjacency list can be constructed in linear time from a list of edges.
We begin by making all the lists empty. When we encounter an edge
, we add an entry consisting of
w
and the cost to
v
's adja-
cency list. The insertion can be anywhere; inserting it at the front can be
done in constant time. Each edge can be inserted in constant time, so the
entire adjacency list structure can be constructed in linear time. Note that
Adjacency lists can
be constructed in
linear time from a
list of edges.
(
vwc
vw
,,
)
c
vw
,
,
figure 14.2
Adjacency list
representation of the
graph shown in
Figure 14.1; the
nodes in list
i
represent vertices
adjacent to
i
and the
cost of the connecting
edge.
0
1
(2)
3
(1)
1
4
(10)
3
(3)
2
0
(4)
5
(5)
4
(2)
6
(4)
5
(8)
2
(2)
3
4
6
(6)
5
6
5
(1)
Search WWH ::
Custom Search