22C:21: Computer Science II: Data Structures

Quiz 7: November 5, 2004

Here is a graph with 5 vertices.

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.