Homework 6: Due 10/18
The current version of the Graph class
implements breadth-first search and related functions.
Specifically, the recent additions to the Graph class
- public int breadthFirstSearch(String source): returns a breadth-first search tree rooted at
source and stored in an int array.
The entry in slot i contains the index of the parent of the vertex with index i.
Since source has no parent, (by convention) the slot with index source is assigned the value
Also, vertices not in the same component as source are assigned -1.
- public boolean isConnected(): returns true if the graph is connected;
- public String connectedComponents():
returns a 2-d array of vertex names representing the connected components
of the graph. Each row in the 2-d array is a connected component and the number
of rows equals the number of connected components.
Using the breadthFirstSearch method,
implement a method to compute and return a shortest path (in hops) between a pair of given vertices.
The method should have the following header:
String shortestPath(String source, String destination)
The String array that is returned should contain a sequence of vertices that corresponds
to a shortest path from the source vertex to the destination vertex.
Thus slot 0 in this String array should contain source and the last
slot in this String array should contain destination.
The length of this array should be exactly equal to the length of a shortest path
from source to destination.
Now implement a program called playLadders.java that plays the Ladders game.
This program should start by reading words.dat and constructing
the Ladders graph.
Then the program should prompt the user and ask them for two 5-letter legal English words.
The program should respond by either outputting a shortest sequence of valid moves in the
Ladders game that will take the first word to the second word or by declaring that is is not
possible to transform the first word into the second word.
The program should be able to do this by calling the shortestPath method in the
Your program should repeat the above until the user is ready to "quit" the game.
If either of the two words typed by the user are not legal 5-letter English words, then the
program should inform the user of this and continue.