Java Reference
In-Depth Information
18.
A
multiple edge
occurs when two vertices are joined by two or more edges in the same direction. Figure 29-6
shows a directed, weighted graph that has a multiple edge from
D
to
B
.
a.
Give an example of a problem in which allowing multiple edges would be useful.
b.
Can an adjacency matrix represent an unweighted graph that has multiple edges?
c.
Can an adjacency matrix represent a weighted graph that has multiple edges?
d.
Can adjacency lists represent an unweighted graph that has multiple edges?
e.
Can adjacency lists represent a weighted graph that has multiple edges?
19.
FIGURE 29-6
A graph for Exercise 18
5
A
B
2
3
5
2
4
C
D
12
P
ROJECTS
1.
Complete the implementation of the class
DirectedGraph
that was begun in Segment 29.16 of this chapter.
2.
Implement a class of undirected graphs by extending the class
DirectedGraph
. What methods should you
override? What methods, if any, in
DirectedGraph
do not apply to an undirected graph? If such methods exist,
what should you do in your new class? Note that the method
getNumberOfEdges
is the only accessor method to
a data field of
DirectedGraph
.
3.
Revise the class
DirectedGraph
by defining protected mutator methods for the data fields
vertices
and
edgeCount
. Also, define a protected accessor method for
vertices
. Then repeat Project 2, using your revised
DirectedGraph
. Compare the performance of the
addEdge
methods in this implementation of an undirected graph
versus the implementation possible under the assumptions of Project 2.
4.
Implement the classes
Vertex
and
DirectedGraph
by using an adjacency matrix.
5.
Assuming an implementation of a class of undirected graphs, implement a method that detects whether an
undirected graph is acyclic. You can look for cycles during either a breadth-first traversal or a depth-first traversal
by discovering an edge to a vertex that is not the predecessor and has already been visited. To simplify the
problem initially, you can assume that the graph is connected. Then remove this assumption.
6.
Implement a method that detects whether a graph is connected.
7.
Create the classes
LimitedVertex
and
LimitedDirectedGraph
that use the representation described in Exercise 14.
8.
A
graph coloring
assigns a color to every vertex in a graph, with the restriction that two vertices of the same
color cannot be adjacent. A graph is said to be
k
-colorable
if it can be colored in
k
or fewer colors.
•
Give an algorithm that will return true if a graph is 2-colorable and false otherwise.
•
Exercise 15 defined a bipartite graph. Show that a graph is bipartite if and only if it is 2-colorable.
Then, using this fact, implement a method that detects whether a graph is bipartite.
9.
Repeat Project 15 in Chapter 13 to create a simple social network. Use a graph to track the friend relationships
among members of the network. Add a feature to enable people to see a list of their friends' friends.
