Java Reference
In-Depth Information
P
ROJECTS
1.
In a search tree, it is easy to search for any value. For other trees in which the children of a node are not ordered in
any particular way, you can use a breadth-first traversal, as described for graphs, to find a path from the root to
some other node (vertex)
v
. Implement such a method for a general tree.
2.
Write Java code that creates the graph given in Figure 28-1. Find the shortest path from Sandwich to Falmouth.
Do the same for the weighted graph in Figure 28-3. (See Exercise 19.)
3.
Write Java code that creates the graph in Figure 28-10. Perform a breadth-first traversal of the graph, beginning at
the node labeled
A
.
4.
In the game of Nim, an arbitrary number of chips are divided into an arbitrary number of piles. Each player can
remove as many chips as desired from any single pile. The last player to remove a chip wins.
Consider a limited version of this game, in which three piles contain 3, 5, and 8 chips, respectively. You can
represent this game as a directed graph. Each vertex in this graph is a possible configuration of the piles (chips in each
pile). The initial configuration, for example, is (3, 5, 8). Each edge in the graph represents a legal move in the game.
a.
Write Java statements that will construct this directed graph.
b.
Discuss how a computer program might use this graph to play Nim.
5.
The
diameter
of an unweighted graph is the maximum of all the shortest distances between pairs of vertices in the graph.
a.
Give an algorithm for computing the diameter of a graph.
b.
What is the Big Oh performance of your algorithm in terms of the number of vertices and edges in the graph?
c.
Implement your algorithm.
d.
Discuss possible ways that you can improve the performance of the algorithm.
6.
Exercise 22 described how to find the critical path in a weighted, directed, acyclic graph. Write a method that will
find the critical path. You may assume the existence of a method that tests whether a graph is acyclic.
7.
The
n-
puzzle is a one-person game that involves a square or rectangular frame that can contain exactly
n
+ 1 square
tiles. The game begins with
n
tiles numbered from 1 to
n
positioned randomly in the frame. With one empty space in
the frame, the objective is to slide the tiles—one at a time and either horizontally or vertically—until they appear in
numerical order, as shown in Figure 28-24a. This solved configuration is for a 15-puzzle using a 4-by-4 frame.
FIGURE 28-24
(a) A solved 15-puzzle; (b) an unsolvable 15-puzzle
(a)
(b)
1
23
4
5678
9 10 11 12
13 15 14
1 234
5678
9
10 11 12
13
14
15
Not all initial configurations of an
n
-puzzle can be solved. For example, if the initial configuration of a
15-puzzle were as pictured in Figure 28-24b, with only the 14 and 15 tiles interchanged, no solution would be
possible. A solvable 15-puzzle can take up to 80 moves to reach the solution; an 8-puzzle using a 3
3 frame will
take at most 31 moves to solve, if it has a solution. To reduce our effort even further, we will consider 5-puzzles in
2
×
3 frames. Figure 28-25 shows two such puzzles with their solutions. Note that the empty space in a solution
can be either before the 1 or after the 5.
Figure 23-22 in Chapter 23 showed a game tree for tic-tac-toe. A game tree, which is a kind of graph,
contains the possible moves for a particular game. Because you cannot change a move made in tic-tac-toe, the
game tree is a directed graph. Such is not the case for the
n
-puzzle, as you can change your mind about any move.
Thus, an undirected graph can represent all of the possible moves.
×
