Quiz 4, Thursday, 10/30

(20 minutes. Open notes)

Suppose that Darth Vader has tampered with your implementation of the queue data structure. When you perform a dequeue operation, you don't get the front of the queue; instead you get the element just behind the front most element. Of course, if the queue has only one element, then that is what you get when you perform a dequeue.

Using the queue so maliciously tampered by Lord Vader, perform breadth first traversal on the graph shown below, starting from vertex A. For the traversal, show (i) the order in which vertices are discovered by breadth first traversal and (ii) the breadth first traversal tree. Assume that the neighbors of each vertex are scanned in alphabetical order of their names.