Java Reference
In-Depth Information
definitions
14.1
A graph consists of a set of vertices and a set of edges that connect the verti-
ces. That is,
G
= (
V
,
E
), where
V
is the set of vertices and
E
is the set of edges.
Each edge is a pair (
v
,
w
), where
v
,
w
∈
V
.
Vertices are sometimes called
nodes
,
and edges are sometimes called
arcs
. If the edge pair is ordered, the graph is
called a
directed graph.
Directed graphs are sometimes called
digraphs
. In a
digraph, vertex
w
is
adjacent
to vertex
v
if and only if (
v
,
w
)
∈
E
. Sometimes
an edge has a third component, called the
edge cost
(or
weight
) that measures
the cost of traversing the edge. In this chapter, all graphs are directed.
A
graph
consists of
a set of vertices
and a set of edges
that connect the
vertices. If the edge
pair is ordered, the
graph is a
directed
graph
.
The graph shown in Figure 14.1 has seven vertices,
Vertex
w
is
adjacent
to vertex
v
if there
is an edge from
v
to
w
.
V
0
V
1
V
2
V
3
V
4
V
5
V
6
=
{
,
,
,
,
,
,
}
and 12 edges,
⎧
(
V
0
V
1
2
,
,
)
,
(
V
0
V
3
1
,
,
)
,
(
V
1
V
3
3
,
,
)
,
(
V
1
V
4
10
,
,
)
⎫
⎪
⎪
E
=
(
V
3
V
4
2
,
,
)
,
(
V
3
V
6
4
,
,
)
,
(
V
3
V
5
8
,
,
)
,
(
V
3
V
2
2
,
,
)
⎨
⎬
⎪
⎪
(
V
2
V
0
4
,
,
)
,
(
V
2
V
5
5
,
,
)
,
(
V
4
V
6
6
,
,
)
,
(
V
6
V
5
1
,
,
)
⎩
⎭
The following vertices are adjacent to
V
3
:
V
2,
V
4,
V
5,
and
V
6
. Note that
V
0
and
V
1
are not adjacent to
V
3
. For this graph,
A
path
is a
sequence of verti-
ces connected by
edges.
V
=
7
and
E
=
12
; here,
S
represents the size of set
S
.
A
path
in a graph is a sequence of vertices connected by edges. In other
words, the sequence of vertices is such that (
w
i
,
w
i
+ 1
)
∈
E
for
. The
path length
is the number of edges on the path—namely,
—also called the
unweighted path length.
The
weighted path length
is
the sum of the costs of the edges on the path. For example,
w
1
w
2
,
,
…
,
w
N
The
unweighted
path length
mea-
sures the number of
edges on a path.
1
iN
N
1
<
-
V
0
V
3
V
5
,
,
is a
figure 14.1
A directed graph
2
V
0
V
1
4
1
3
10
V
2
V
3
V
4
2
2
5
8
4
6
V
5
V
6
1
Search WWH ::
Custom Search