CS410, Summer 1998
Quiz #13
August 3

Consult no sources.				Name:

1. The breadth-first search algorithm maintains several things including:
   * a queue of vertices
   * a distance value for each vertex.
What invariant about the distance values of the vertices currently in
the queue is maintained by the algorithm?

2. What is the algorithm for depth-first search of a graph?

3. What is the asymptotic running time for depth-first search of a graph?

ANSWERS
=======

1. [2 points] The distances differ by at most one and the ones with
   lower distances are at the front of the queue.

2. [4 points] 

  dfs(v)
     arrive[v] = time++;
     for each edge (v,u) out of v:
	if (!visited[u])
	   visited[u] = true;
	   dfs(u);
     leave[v] = time++;

3. [4 points]
  O(n+m) where n is the number of vertices and m is the number of
  edges in the graph.