Exercise 22.2-1

Show the d and p values that result from running breadth-first search on the directed graph of Figure 22.2(a), using vertex 3 as the source.

p Values

# Exercise 22.2.2

Show the d and p values that result from running breadth-first search on the undirected graph of Figure 22.3, using vertex u as the source.

Answer: Similar to the answer in 22.1-1. After run through the algorithm BFS(G,s) we have the final results as follow:

r                 s             t                  u

 d Values

v                 w            x                y

 p Values

Exercise 22.2-6

There are two types of professional wrestlers: "good guys" and "bad guys." Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n + r)-time algorithm that determines whether it is possible to designate some of the wrestlers as good guys and the remainder as bad guys such that each rivalry is between a good guy and a bad guy. If it is possible to perform such a designation, your algorithm should produce it.