Java Reference
In-Depth Information
FIGURE 28-3
A weighted graph
10
Provincetown
Truro
17
Orleans
Sandwich
Barnstable
19
9
12
20
4
19
Chatham
Falmouth
Hyannis
Question 1
Consider the graph in Figure 28-3.
a.
What is the length of the path that begins in Provincetown, passes through Truro and
Orleans, and ends in Chatham?
b.
What is the weight of the path just described?
c.
Consider all paths from Truro to Sandwich that do not have cycles. Which path has the
shortest length?
d.
Of the paths you considered in Part
c
, which one has the smallest weight?
28.4
Connected graphs.
The towns on a road map are connected by roads in a way that enables you to
go from any town to any other town. That is, you can get from here to there. A graph that has a path
between every pair of distinct vertices is
connected
. A
complete graph
goes even further; it has an
edge between every pair of distinct vertices. Figure 28-4 provides examples of undirected graphs
that are connected, complete, or
disconnected
—that is, not connected. Notice the simple path in
Part
a
and the simple cycle in Part
c
.
FIGURE 28-4
Undirected graphs
(a)
(b)
(c)
A
Simple path
from A to B
Simple cycle
B
Connected
Complete
Disconnected
28.5
Adjacent vertices.
Two vertices are
adjacent
in an undirected graph if they are joined by an edge.
In Figure 28-3, Orleans and Chatham are adjacent, but Orleans and Sandwich are not. Adjacent
vertices are called
neighbors
. In a directed graph, vertex
i
is adjacent to vertex
j
if a directed edge
