## Graph Traversal: Breadth First Seach and Depth First Search

I don't understand BFS and DFS. How do I visit the vertex and mark it as visited? Not sure how to do DFS with an arraylist of iterators. Need to some how iterate through the adjacency list for each vertex.

Code:
```public class Graph
{
// translate integer vertex to string name
private final List<String> vertexName = new ArrayList<String>();
// translate name to integer form of vertex
private final Map<String, Integer> nameToVertexMap = new HashMap<String, Integer>();
// represent adjacency list of the graph
private final List<List<Integer>> adjacencyList = new ArrayList<List<Integer>>();

// Reads data from a scanner and builds the graph.
public void buildGraph(Scanner sc)
{
while (sc.hasNext())
{
// get data for the adjacency list of one vertex
String initVertexName = sc.next();
int initVertex = this.getVertexForName(initVertexName);
if (initVertex == -1)
// get the outdegree
int outDegree = sc.nextInt();
// collect list of neighbors for this vertex
for (int k = 0; k < outDegree; k++)
{
// get the string name of the terminal vertex for an edge
String finalVertexName = sc.next();
//get the vertex number for this vertex name
int finalVertex = this.getVertexForName(finalVertexName);
// if the vertex name has no number, get it a number
if (finalVertex == -1)
}
}
}

// string representation of the adjacency list of the graph
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
for (int v = 0; v < this.adjacencyList.size(); v++)
{
sb.append(this.vertexName.get(v) + " : ");
sb.append(vertexName.get(i) + " ");
sb.append("\n");
}

return sb.toString();
}

/**
* @param vertex: integer representation of a vertex.
* @return the adjacency list for a specified vertex
*/
public List<Integer> getNeighbors(int vertex)
{
}

// returns the number of vertices in this graph
public int getNumberOfVertices()
{
}

// returns string name of the vertex to use for output.
public String getVertexName(int vertex)
{
return vertexName.get(vertex);
}

/**
* @param name: name of a vertex, read from an input stream or scanner
* @return the integer (vertex) assigned to that name, or -1 if no integer
*         vertex has been assigned to that name.
*/
public int getVertexForName(String name)
{
return vertexName.indexOf(name);
}

/**
* Adds a new vertex with a given name to the graph and associates
* the string name of the vertex with an integer used to identify the vertex.
* @param name: string name for a vertex
* @return an integer value that will be used to identify the vertex.
*/
{
int vertex = getVertexForName(name);
if (vertex != -1) throw new IllegalStateException("There is already a " +
"vector with name " + name);
// The integer associated with the name is its index in the list vertexName
vertex = vertexName.size() - 1;
nameToVertexMap.put(name, vertex);

return vertex;
}
}```
Code:
```public class GraphTraversal
{
/**
* This version of BFS will stop as soon as it finds a path from the source
* to the destination.
* @param source: the vertex where the search should begin.
* @param dest: the vertex where the search should end.
* @param graph: the graph to be searched.
* @param visited: a boolean array used to mark vertices when they are
*                 visited.
* @param pred: an integer array that assigns to each vertex its predecessor
*              in the path that is found.
*/
static void breadthFirstSearch(int source, int dest, Graph graph,
boolean [] visited, int [] pred)
{
visited = new boolean [graph.getNumberOfVertices()];
pred = new int [graph.getNumberOfVertices()];

// visit source
// mark source
q.offer(source);

while(!q.isEmpty())
{
int f = q.peek();
List<Integer> w = graph.getNeighbors(f);
for(int i : w)
{
// visit w
// mark w
}
}
q.remove();
}

// This version of DFS will stop as soon as it finds a path from the source to the destination.
static void depthFirstSearch(int source, int dest, Graph graph,
boolean [] visited, int [] pred)
{
ArrayList<Iterator> i = new ArrayList<Iterator>();
}

/**
* breadthFirst performs a BFS of a graph.
* @param source: the initial vertex for the search
* @param graph: This is the graph to be traversed
* @param visited: this array indicates which vertices have been visited.
*                 BFS will set visited[v] = for only those vertices that were
*                 visited. Here v is the index that identifies a vertex in
*                 the graph.
* @param pred: for each vertex v that is visited, pred[v] will be set to its
*              predecessor, that is, the vertex that led to v in the BFS.
*/
static void breadthFirstSearch(int source, Graph graph, boolean [] visited,
int [] pred)
{
pred);
}

static void breadthFirstSearch(String s_source, Graph graph,
boolean [] visited, int [] pred)
{
int source = graph.getVertexForName(s_source);
pred);
}

static void breadthFirstSearch(String s_source, String s_dest, Graph graph,
boolean [] visited, int [] pred)
{
int source = graph.getVertexForName(s_source);
int dest = graph.getVertexForName(s_dest);
}

static void depthFirstSearch(String source, Graph graph, boolean[] visited,
int [] pred)
{
int sourceVertex = graph.getVertexForName(source);
depthFirstSearch(sourceVertex, graph.getNumberOfVertices(), graph,
visited, pred);
}

static void depthFirstSearch(int source, Graph graph, boolean [] visited,
int [] pred)
{
depthFirstSearch(source, graph.getNumberOfVertices(), graph, visited,
pred);
}

static void depthFirstSearch(String source, String dest, Graph graph,
boolean [] visited, int [] pred)
{
int sourceVertex = graph.getVertexForName(source);
int destVertex = graph.getVertexForName(dest);
depthFirstSearch(sourceVertex, destVertex, graph, visited, pred);
}

/**
* getPath finds the path that goes from a given start vertex to a
*         given destination vertex
* @param source: the start vertex for a path.
* @param dest: the end vertex for a path.
* @param pred: an array that specifies the predecessor of each vertex in
*              a path. If a vertex has no predecessor in the path, its
*              predecessor is null.
* @return a list of vertices that form a path from a source vertex to
*         a destination vertex.
*/
public static List<Integer> getPath(int source, int dest, int [] pred)
{
int current = dest;
while (current != source)
{
current = pred[current];
if (current == -1)
{
path.clear();
return path;
}
}

return path;
}

/**
* getPath finds a path from a given start vertex to a given destination vertex.
* It allows the vertices to be specified by name instead of by numeric values.
* @return a list of vertex names for the vertices on the path.
*/
static List<String> getPath(String source, String dest, int [] pred, Graph graph)
{
int sourceVertex = graph.getVertexForName(source);
int destVertex = graph.getVertexForName(dest);
List<Integer> path = getPath(sourceVertex, destVertex, pred);
List<String> sPath = new ArrayList<String>();
for (int i : path)