This homework is about graphs.

[50 points] First, build an adjacency list implementation for graphs. In particular, your program should input graph files with the following format:

       int       //number of vertices n
       [int]     //edges emanating from vertex 0
       [int]     //edges emanating from vertex 1
       ...
       [int]     //edges emanating from vertex n-1

The notation [int] indicates the line contains zero or more integers -- a blank line therefore means that the corresponding vertex has no outgoing edges. A graph file contains n+1 lines; the first is the number of vertices n followed by a line for each of the n vertices. Sample code to read a graph file, along with a sample graph file, is in ~lorenz/cs35-2/hw8/. You will need to modify this code since it only reads and prints the graph. Also, note that although this supplied code returns vertex lines as an integer array, your graph representation should use lists; i.e., when reading vertex v, call addEdge(v, i) for all i on v's line.

Second, implement either depth-first or breadth-first search for your graph representation. For each vertex in the graph, print out the vertex number and the vertices reachable from it. That is, run n searches, one starting at each graph vertex. Be sure to reset per-vertex information (such as colors) before each search.

While writing your program, test it with graph files you create. On April 25, I'll make a large graph file available (script-graph); the operation of your search on this file is to be scripted for submission.

Hand in: code for the entire program and the script of it searching the file script-graph.
instructions on how to submit