Graphs - Data Structures and Abstractions with Java - page 729

Since you can travel in both directions along the roads in Figure 28-1, the corresponding graph
and its edges are said to be undirected . But cities often have one-way streets. The graph in
Figure 28-2 has a vertex for each intersection in a city's street map. The edges each have a direction
and are called directed edges . A graph with directed edges is called a directed graph , or digraph .
You can transform an undirected graph into a directed graph by replacing each undirected edge
with two directed edges that have opposite directions.

VideoNote

Graph concepts and
terminology

FIGURE 28-2

A directed graph representing a portion of a city's street map

28.2

Paths. A path between two vertices in a graph is a sequence of edges. A path in a directed graph
must consider the direction of the edges, and is called a directed path . The length of a path is the
number of edges that it comprises. If the path does not pass through any vertex more than once, it is
a simple path . Figure 28-1 contains a simple path from Provincetown to Orleans of length 2.
A cycle is a path that begins and ends at the same vertex. A simple cycle passes through other
vertices only once each. In Figure 28-1, the cycle Chatham-Hyannis-Barnstable-Orleans-Chatham
is a simple cycle. A graph that has no cycles is acyclic .
You use a road or street map to see how to get from point A to point B. The path you choose
between these points will usually be a simple path. In doing so, you avoid retracing your steps or
going around in circles. People who take a ride to view the autumn leaves, however, would follow a
cycle that begins and ends at home.

28.3

Weights. You might be happy just to get from one place to another, but you often have a choice of
several paths. You could choose the shortest, the fastest, or the cheapest path, for example. To do
so, you use a weighted graph , which has values on its edges. These values are called either
weights or costs . For example, Figure 28-3 shows the road map from Figure 28-1 as a weighted
graph. In this version, each weight represents the distance in miles between two towns. Other types
of weights you might use could represent the driving time or the cost of traveling by taxi.
A path in a weighted graph also has a weight, or cost, that is the sum of its edge weights. For
example, the weight of the path from Provincetown to Orleans in Figure 28-3 is 27.