We can modify BFS to traverse edge (u,v) twice. The first time is the tree edge (u,v), and the second time is (v,u).
June 20, 2007
Exercises 22.2-7
BFS from one node s and we can get a node u with maximum d value. Then do BFS from u, find out the node v with maximum d value. It is the solution.
Exercises 22.2-6
The problem is the same as recognizing bipartite graph. Set a node s as good guy, than all its rivals are bad guys. All bad guys’ rivals must be good guys. If there exists one pair violates this constraint then return No, otherwise return Yes.
Exercises 22.2-5
G = ({s,u,v,w,x}, {(s,u),(s,v),(u,w),(v,x),(u,x),(v,w)}). 
Exercises 22.2-4
Because d[u] is the distance from s to u, it must be unique. But the BFS tree depends on the order in the adjacency list.
.