CPSC 411: Quiz 7
October 9, 2008

Printed Name:________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."

Signature:___________________________________________

    Consider this graph:










  1. (2 pts) Draw the spanning tree resulting from running breadth-first search on the graph above. Start with node A and consider each neighboring node in alphabetical order.










  2. (2 pts) Draw the spanning tree resulting from running depth-first search on the graph above. Start with node A and consider each neighboring node in alphabetical order.










  3. (1 pt) What is the running time of breadth-first-search on a graph G = (V,E), in terms of number of nodes and number of edges?