Today we introduce hw3 and BFS, breadth first search.
For both topics, we use a big movie/actor graph defined by
../book/movies.txt (from the IMDB database).

BFS (breadth first search) is used for finding all shortest paths from
some fixed start vertex, in linear time.  It builds a "paths tree"
structure very much like DFS, except that these are shortest paths.  A
fun example BFS application is for solving the "Kevin Bacon" game (a
movie trivia game, see also http://oracleofbacon.org/):

$ cd ../book/
$ run DegreesOfSeparation movies.txt / 'Bacon, Kevin'
+ java -cp '.:*' DegreesOfSeparation movies.txt / 'Bacon, Kevin'
Grant, Cary
   Bacon, Kevin
   Planes, Trains & Automobiles (1987)
   Martin, Steve (I)
   Dead Men Don't Wear Plaid (1982)
   Grant, Cary
^D
$

This program finds shortest paths in the movie-actor graph.  It uses a
BreadthFirstPaths object, to find shortest paths from "Bacon, Kevin".
Then for each name we enter, it reports the shortest path (if there is
one), much as we did already saw for DFS.  Notice that we input the
Graph via a SymbolGraph (a Graph, together with a symbol table and
array, mapping back and forth between names and vertex ids).  Note the
SymbolGraph also helps us to translate the vertex ids back to names,
when we print them out.

See files:
   ../book/movies.txt
   ../book/SymbolGraph.java
   ../book/DegreesOfSeparation.java

   ../book/BreadthFirstPaths.java    [delay, after hw3!]

Before we get into the details of how BFS actually works, we
should introduce hw3, and in particular ../hw3/Movies.java

After that, if there is time, we'll return to talk about the details
of how and why BFS works.  We may return to the 4.1 slides for that.