Name:________________________________________

Consider the following undirected graph:

1. (2 pts) Draw the breadth-first search tree resulting from running BFS on the above graph, starting at node s. Assume that neighbors are checked in alphabetical order.
   
   
   
   
   
   
   
   
   
   
2. (2 pts) Draw the depth-first search tree resulting from running DFS on the above graph, starting at node s. Assume that neighbors are checked in alphabetical order.
   
   
   
   
   
   
   
   
   
3. (1 pt) What is the asymptotic running time of breadth-first search on a graph G = (V,E) as a function of |V| and |E|? Assume the graph is represented with the adjacency list data structure.