CPSC 220 Fall 2005
Program 4: Winning Paths
Overview
In the last program you developed a rating system for a set of
lacrosse teams. In this program you will look for
paths by which one
team indirectly "beats" another.
Assignment
Write a program that prompts the user for the codes for two teams -- a
"winner" and a "loser" -- and prints a list of games that provide the
shortest "winning path" between them. That is, if the "winner" is Teami
and
the "loser" is Teamj, you should print a list of games
in which Teami beats Team1, Team1 beats
Team2,...,
Teamn-1 beats Teamn, and Teamn beats
Teamj. In
the shortest case n=0, that is, Teami beats Teamj
directly.
Provide team codes, team names,
date and score for each game.
If no such path exists,
print an appropriate message.
Program Structure
You should construct a directed, unweighted
graph representing the games played, where
an edge from team A to team B indicates that A beat B in a game.
You may choose the graph representation you want to use, but you must
justify your choice. You can do this in the documentation in the
graph class (and be sure that your graph code is neatly
encapsulated in its own class).
Note that
team A could beat team B more than once in a single season (and this does
occur in our data); in this case you can use any of the relevant
games to represent
the A->B edge in the graph.
Use the BFS algorithm discussed in class to find the shortest
path from one vertex to another. Note that you don't need to use Dijkstra's
algorithm for this, as the edges are unweighted. Your code should be
clean and reasonably efficient.
What to Turn In
Turn in hardcopy of your program and e-mail me a tar file of the program.