Java Reference
In-Depth Information
FIGURE 28-6
Airline routes
Boston
Provincetown
Providence
Naples
Miami
Hyannis
Key West
Nantucket
Martha's Vineyard
28.8
Mazes have been constructed in Victorian English gardens and modern-day cornfields. A typical
maze, like the one in Figure 28-7a, has a path from its entrance to its exit. Other paths begin at
the entrance, but some lead to dead ends, rather than to the exit. Can you find your way through
the maze?
We can represent this maze as a graph by placing a vertex at the entrance and exit, at each turn in
the path, and at each dead end, as Figure 28-7b shows. This graph, like the road map in Figure 28-1,
is connected. For such graphs, we can find a path between any two vertices, as you will see later in
this chapter.
FIGURE 28-7
(a) A maze; (b) its representation as a graph
(a)
Entrance
(b)
Exit
28.9
As a college student, you must take a sequence of courses in your major. Each course has certain
prerequisite courses that you must complete first. In what order can you take the required courses
and satisfy the prerequisites?
