Java Reference
In-Depth Information
10.
Implement the method
getDepthFirstTraversal
. Segment 28.13 of the previous chapter presents the
pseudocode for this method. What is its Big Oh?
11.
Implement the method
getCheapestPath
for a weighted graph. The pseudocode for this method appears in
Segment 28.24 of the previous chapter. What is its Big Oh?
12.
Draw a class diagram that shows the relationships among the classes
DirectedGraph
,
Vertex
, and any other
supporting classes such as
LinkedDictionary
.
13.
The
out degree
of a vertex is the number of edges that originate at the vertex. The
in degree
of a vertex is the
number of edges that terminate at the vertex. Modify the class
DirectedGraph
so that it can compute the in degree
and out degree of any of its vertices.
14.
Suppose that you have a weighted, directed graph in which the out degree and in degree of every vertex is at most 4.
(See the previous exercise.) If the graph has
n
vertices, you could represent it by using an array that has
n
rows and
4 columns. Each of the
n
rows is associated with a different vertex in the graph. The entries in a row associated with
vertex
v
are the vertices at the ends of the edges that begin at
v
. Since the out degree of a vertex can be less than 4,
some entries in a row might be
null
.
What is the Big Oh of each of the following operations?
a.
Testing whether two given vertices are adjacent
b.
Finding all vertices adjacent to a given vertex
15.
A graph is said to be
bipartite
if the vertices can be divided into two groups such that every edge goes from a
vertex in one group to a vertex in the other group. Figure 28-1 of the previous chapter contains a bipartite graph.
We could put Sandwich, Hyannis, Orleans, and Provincetown in group
A
, and Barnstable, Falmouth, Chatham,
and Truro in group
B
. Every edge goes from a vertex of group
A
to a vertex of group
B
.
a.
Which of the graphs in Figure 28-4, 28-6, and 28-7b are bipartite?
b.
How might the implementation of a bipartite graph differ from that of a regular graph to take advantage of
its bipartite nature?
n
2
.
a.
What is the time complexity, using Big Oh notation, for each of the following operations when an adja-
cency matrix is used to represent the graph?
•
16.
Consider a directed graph that has
n
nodes and
e
edges, where 0
≤
e
≤
Testing whether two vertices are joined by an edge
•
Finding the successors of a given vertex
•
Finding the predecessors of a given vertex
b.
Repeat part
a
, but assume that the graph uses an adjacency list in its implementation instead of an adja-
cency matrix.
17.
A
loop
is an edge that starts and ends at the same vertex. Figure 29-5 shows an example of a loop in a directed,
weighted graph.
a.
Give an example of a problem where allowing loops would be useful.
b.
Can the adjacency matrix and adjacency list representations of a graph support loops?
FIGURE 29-5
A graph for Exercise 17
5
2
A
B
Loop
1
