Hints for Question 1

You can modify the algorithm to compute a breadth first search tree to solve this question. The algorithm is posted in the course's website.

Try to solve the problem with the above hint. If you really do not see how to design the algorithm, here is are additional hints.