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.
- Show the depth-first tree for this graph.
- Show the breadth-first tree for this graph.
- 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.