Java Reference
In-Depth Information
4.
In what order does a breadth-first traversal visit the vertices in the graph in Figure 28-10 when you begin at
a.
Ve r t e x
G
b.
Ve r t e x
F
5.
Repeat the previous exercise, but perform a depth-first traversal instead.
6.
Consider the directed graph that appears in Figure 28-10, and remove the edge between vertices
E
and
F
, and the
edge between vertices
F
and
H
.
a.
In what order will a breadth-first traversal visit the vertices when you begin at vertex
A
?
b.
Repeat Part
a
, but perform a depth-first traversal instead.
7.
Draw a directed graph that depicts the prerequisite structure of the courses required for your major. Find a
topological order for these courses.
8.
Construct the topological ordering for the weighted, directed, acyclic graph in Figure 28-23.
FIGURE 28-23
A graph for Exercises 8 and 22
5
1
3
4
A
B
C
D
E
4
5
2
3
F
G
H
12
1
3
4
2
I
J
K
1
7
L
M
9.
A computer network such as the Internet or a local area network can be represented as a graph. Each computer is
a vertex in the graph. An edge between two vertices represents a direct connection between two computers.
Explain when and why you would be interested in each of the following tasks:
a.
Finding a path in this graph
b.
Finding multiple paths from one particular vertex to another
c.
Finding the shortest path from one particular vertex to another
d.
Seeing whether the graph is connected
10.
Write an algorithm that finds a path from vertex
a
to vertex
b
in a directed graph by using a slightly modified
depth-first traversal. Segment 28.16 outlines an approach to this problem.
11.
A tree is a connected graph without cycles.
a.
What is the smallest number of edges that could be removed from the graph in Figure 28-1 to make it a tree?
b.
Give one example of such a set of edges.
12.
Figure 28-7b shows a graph that represents a maze. Label the vertices of this graph, with the uppermost vertex
labeled
S
(the entrance to the maze) and the lowest vertex labeled
T
(the exit from the maze).
a.
Is this graph a tree?
b.
What is the shortest path from
S
to
T
?
c.
What is the longest simple path in this graph?
