Java Reference
In-Depth Information
when all vertices are in the tree. Design and implement an algorithm for finding
an MST using Kruskal's algorithm.
*29.2
(
Implement Prim's algorithm using an adjacency matrix
) The text implements
Prim's algorithm using lists for adjacent edges. Implement the algorithm using
an adjacency matrix for weighted graphs.
*29.3
(
Implement Dijkstra's algorithm using an adjacency matrix
) The text imple-
ments Dijkstra's algorithm using lists for adjacent edges. Implement the algo-
rithm using an adjacency matrix for weighted graphs.
*29.4
(
Modify weight in the nine tails problem
) In the text, we assign the number of
the flips as the weight for each move. Assuming that the weight is three times
of the number of flips, revise the program.
*29.5
(
Prove or disprove
) The conjecture is that both
NineTailModel
and
WeightedNineTailModel
result in the same shortest path. Write a program to
prove or disprove it. (
Hint
: Let
tree1
and
tree2
denote the trees rooted at node
511
obtained from
NineTailModel
and
WeightedNineTailModel
, respec-
tively. If the depth of a node
u
is the same in
tree1
and in
tree2
, the length of
the path from
u
to the target is the same.)
**29.6
(
Weighted 4
*
4 16 tails model
) The weighted nine tails problem in the text
uses a 3
4 matrix.
Create a new model class named
WeightedTailModel16
. Create an instance
of the model and save the object into a file named
WeightedTailModel16.dat
.
*
3 matrix. Assume that you have 16 coins placed in a 4
*
**29.7
(
Weighted 4
*
4 16 tails
) Revise Listing 29.9, WeightedNineTail.java, for the
weighted 4
4 16 tails problem. Your program should read the model object
created from the preceding exercise.
*
**29.8
(
Traveling salesperson problem
) The traveling salesperson problem (TSP) is
to find a shortest round-trip route that visits each city exactly once and then
returns to the starting city. The problem is equivalent to finding a shortest
Hamiltonian cycle in Programming Exercise 28.17. Add the following method
in the
WeightedGraph
class:
// Return a shortest cycle
// Return null if no such cycle exists
public
List<Integer> getShortestHamiltonianCycle()
*29.9
(
Find a minimum spanning tree
) Write a program that reads a connected graph
from a file and displays its minimum spanning tree. The first line in the file
contains a number that indicates the number of vertices (
n
). The vertices are
labeled as
0
,
1
, ...,
n-1
. Each subsequent line describes the edges in the form
of
u1, v1, w1 | u2, v2, w2 | ...
. Each triplet in this form describes
an edge and its weight. Figure 29.24 shows an example of the file for the cor-
responding graph. Note that we assume the graph is undirected. If the graph has
100
0
1
File
6
0, 1, 100 | 0, 2, 3
1, 3, 20
2, 3, 40 | 2, 4, 2
3, 4, 5 | 3, 5, 5
4, 5, 9
3
20
40
2
3
5
2
5
9
4
5
(a)
(b)
F
IGURE
29.24
The vertices and edges of a weighted graph can be stored in a file.
Search WWH ::
Custom Search