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?