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

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

Figure 22.2 Two representations of a directed graph. (a) A directed graph G with 6 vertices and 8 edges. (b) An adjacency-list representation of G. (c) The adjacency-matrix representation of G.

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

Figure 22.3 The operation of BFS on an undirected graph. Tree edges are shown shaded as they are produced by BFS. The value of u.d appears within each vertex u. The queue Q is shown at the beginning of each iteration of the while loop of lines 10–18. Vertex distances appear below vertices in the queue.