$18\mathrm{.}1$ Lab $16$: Graph BFS

In this Lab we continue developing our Graph class by adding breadth$-$first search $($BFS$).$

Step $1$: Setup

$-$ Copy your completed Graph class from Lab $15$ into the Graph $.$ java file below.

$-$ Copy your LinkedList class from Lab $15$ into the LinkedList. java file below. Recall that the LinkedList is used to store adjacent vertices at each vertex in the Graph.

$-$ Inspect the LabProgram, which allows you to test each method of Graph in Develop Mode as you write your code. Automatic testing in Submit mode requires completion of most methods of this lab.

Step $2$: Complete the BFS method of the Graph class to implement breadth$-$first search.

Follow the guidance given in the block comment for the method and class notes.

Step $3$: Test the BFS $()$ method and updates

After finishing BFS$,$ the following methods will produce more results and will be tested more completely in both the LabProgram and unit testing:

$-$ testGetDistance$()$

$-$ testGetParent$()$

$-$ testGetColor$()$ Parallel Arrays for BFS

$-$ Your Graph will store information not only about adjacent vertices.

$-$ It will also store data about the color, parent and the distance $($from the source$)$ of all the vertices in the Graph for tracing the BFS algorithm and color, parent, discovery time, and finish time for the DFS algorithm.

Inside your Graph class, there are six private ArrayLists to store this data:

$```$

private ArrayList $>$ adj;

private ArrayList color;

private ArrayList distance;

private ArrayList parent;

private ArrayList discoverTime;

private ArrayList finishTime;

$```$

These ArrayLists are in parallel to each other. For example:

$```$

adj.get$(1)$

color.get$(1)$

distance.get$(1)$

parent.get$(1)$

$```$

These all store information about vertex $1$ of the Graph and are updated and used in the BFS$()$ method. $```$

$/**$

$*$ Performs breath first search on this Graph give a source vertex

$*$

$*$ @param source the starting vertex

$*$ @precondition source is a vertex in the graph

$*$ @throws IndexOutOfBoundsException when the source vertex is out of bounds

$*$ of the graph

$*/$

public void BFS$($Integer source$)$ throws IndexOutOfBoundsException $\{$

$\}$

$/**$

$*$ Performs depth first search on this Graph in order of vertex lists

$*/$

public void DFS$()\{$

$\}$

$/**$

$*$ Private recursive helper method for DFS

$*$

$*$ @param vertex the vertex to visit

$*/$

private void visit$($int vertex$)\{$

$\}$

$```$