Java Reference
In-Depth Information
path from vertex to . The path length is two edges—the shortest path
between and , and the weighted path length is 9. However, if cost is
important, the weighted shortest path between these vertices has cost 6 and is
. A path may exist from a vertex to itself. If this path contains
no edges, the path length is 0, which is a convenient way to define an other-
wise special case. A
simple path
is a path in which all vertices are distinct,
except that the first and last vertices can be the same.
A
cycle
in a directed graph is a path that begins and ends at the same ver-
tex and contains at least one edge. That is, it has a length of at least 1 such that
; this cycle is simple if the path is simple. A
directed acyclic graph
(DAG)
is a type of directed graph having no cycles.
An example of a real-life situation that can be modeled by a graph is the
airport system. Each airport is a vertex. If there is a nonstop flight between
two airports, two vertices are connected by an edge. The edge could have a
weight representing time, distance, or the cost of the flight. In an undirected
graph, an edge (
v, w
) would imply an edge (
w, v
). However, the costs of the
edges might be different because flying in different directions might take
longer (depending on prevailing winds) or cost more (depending on local
taxes). Thus we use a directed graph with both edges listed, possibly with dif-
ferent weights. Naturally, we want to determine quickly the best flight
between any two airports;
best
could mean the path with the fewest edges or
one, or all, of the weight measures (distance, cost, and so on).
A second example of a real-life situation that can be modeled by a graph
is the routing of electronic mail through computer networks. Vertices repre-
sent computers, the edges represent links between pairs of computers, and the
edge costs represent communication costs (phone bill per megabyte), delay
costs (seconds per megabyte), or combinations of these and other factors.
V
0
V
5
The
weighted path
length
is the sum of
the edge costs on a
path.
V
0
V
5
V
0
V
3
V
6
V
5
,
,
,
A
cycle
in a directed
graph is a path that
begins and ends at
the same vertex and
contains at least
one edge.
w
1
=
w
N
A
directed acyclic
graph
has no cycles.
Such graphs are an
important class of
graphs.
For most graphs, there is likely at most one edge from any vertex
v
to any
other vertex
w
(allowing one edge in each direction between
v
and
w
). Conse-
quently, . When most edges are present, we have . Such
a graph is considered to be a
dense graph
—that is, it has a large number of edges,
generally quadratic.
In most applications, however, a
sparse graph
is the norm. For instance,
in the airport model, we do not expect direct flights between every pair of air-
ports. Instead, a few airports are very well connected and most others have
relatively few flights. In a complex mass transportation system involving buses
and trains, for any one station we have only a few other stations that are directly
reachable and thus represented by an edge. Moreover, in a computer network
most computers are attached to a few other local computers. So, in most
cases, the graph is relatively sparse, where or perhaps slightly
more (there is no standard definition of sparse). The algorithms that we
develop, then, must be efficient for sparse graphs.
A graph is
dense
if
the number of
edges is large
(generally qua-
dratic). Typical
graphs are not
dense. Instead, they
are
sparse
.
EV
2
≤
E
=
Θ
(
V
2
)
E
=
Θ
()
V
Search WWH ::
Custom Search