Java Reference
In-Depth Information
HHH
THT
TTT
TTT
TTT
TTT
The number of flips is 8
The program prompts the user to enter an initial node with nine letters with a combination of
H
s and
T
s as a string in line 8, obtains an array of characters from the string (line 9), creates a
model (line 11), obtains the shortest path from the initial node to the target node (lines 12-13),
displays the nodes in the path (lines 16-17), and invokes
getNumberOfFlips
to get the
number of flips needed to reach the target node (line 20).
29.15
✓
✓
Why is the
tree
data field in
NineTailModel
in Listing 28.13 defined protected?
Check
29.16
Point
How are the nodes created for the graph in
WeightedNineTailModel
?
29.17
How are the edges created for the graph in
WeightedNineTailModel
?
K
EY
T
ERMS
Dijkstra's algorithm 1078
edge-weighted graph 1063
minimum spanning tree
shortest path 1078
single-source shortest path
1079
1072
vertex-weighted graph
1063
Prim's algorithm
1072
C
HAPTER
S
UMMARY
1.
You can use adjacency matrices or lists to store weighted edges in graphs.
2.
A spanning tree of a graph is a subgraph that is a tree and connects all vertices in the graph.
3.
Prim's algorithm for finding a minimum spanning tree works as follows: the algorithm starts
with a spanning tree that contains an arbitrary vertex. The algorithm expands the tree by
adding a vertex with the minimum-weight edge incident to a vertex already in the tree.
4.
Dijkstra's algorithm starts search from the source vertex and keeps finding vertices that have
the shortest path to the source until all vertices are found.
Q
UIZ
P
ROGRAMMING
E
XERCISES
*29.1
(
Kruskal's algorithm
) The text introduced Prim's algorithm for finding a mini-
mum spanning tree. Kruskal's algorithm is another well-known algorithm for
finding a minimum spanning tree. The algorithm repeatedly finds a minimum-
weight edge and adds it to the tree if it does not cause a cycle. The process ends
Search WWH ::
Custom Search