Breadth-First Search: (a) (10pt) Consider how breadth-first search works on the following graph, vising nodes in alphabetical order and using A as the source. A B C D E F What is the resulting BFS tree? Also, fill in a table that lists the value of the queue at each point where a vertex is ejected from the queue. The first row is written for you. Node ejected Queue value A B, D (b) (10pt) Suppose you are given a weighted undirected graph G. In class, we used a counterexample to demonstrate why BFS cannot be used to solve the single-source shortest path problem on G. What if you are also told that G is a tree? Either give a counter example to show that BFS still does not work, or argue why BFS will solve the problem correctly.

(20 pts.) Breadth-First Search: (a) (10pt) Consider how breadth-first search works on the following graph, vising nodes in alphabetical order and using A as the source. What is the resulting BFS tree? Also, fill in a table that lists the value of the queue at each point where a vertex is ejected from the queue. The first row is written for you. (b) (10pt) Suppose you are given a weighted undirected graph G. In class, we used a counterexample to demonstrate why BFS cannot be used to solve the single-source shortest path problem on G. What if you are also told that G is a tree? Either give a counter example to show that BFS still does not work, or argue why BFS will solve the problem correctly