CS-151 Labs
Lab 10. Everything is better with Bacon. Graph traversals
10:00pm, Friday, December 9. You may work with a partner on this assignment.
The learning goals for this lab are to
- choose and implement an appropriate graph representation for a given application;
- implement breadth first search on a graph; and
- design your own implementation of a data structure for a specific application.
You will create the following Java files:
BaconNumber.javaGraph.javaVertex.javaGraphTest.java- Any other files for classes that you find helpful
Introduction
In class, we have been discussing how graph structures can be used to represent relationships between groups of objects. For this assignment, you will be writing a program that allows you to play the Kevin Bacon Game. A person’s Bacon Number is computed based on the number of movies of separation between that person and the actor Kevin Bacon. For example, if you are Kevin Bacon, then your Bacon Number is 0. If you were in a movie with Kevin Bacon, your number would be 1. If you weren’t in a movie with Kevin Bacon, but were in a movie with someone who was, your Bacon Number would be 2. In short, your Bacon Number is one greater than the smallest Bacon Number of any of your co-stars.
For fun and some additional background, you can try out the Oracle of Bacon at the University of Virginia.