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 are:

  1. 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.

  2. 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 Graph class. 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.