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:
- (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 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.
- (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?