Quiz 7: November 5, 2004

Below you will be asked to show traversal trees for this graph. For these traversals you should assume that (i) each traversal starts at vertex A and (ii) the neighbors of every vertex are considered in alphabetical order.

1. Show the depth-first tree for this graph.
   

2. Show the breadth-first tree for this graph.
   

3. Now assume that someone has tampered with the implementation of the Queue class such that whenever the queue has 2 or more elements, it returns the second element, rather than the first. If the queue has only one element, then that is what is returned. Show the breadth-first tree for the above graph when the breadth-first traversal uses this tampered implementation of the Queue class.
   

   ---