25

We are running graph searches on the graph below and assuming that the searches visit the adjacent neighbors of a node and the sources in numerical order (smaller first) (a) Draw the breadth-first search tree starting from vertex 1. Give the distance from the source to each vertex computed by the algorithm, i.e., d[v] for v = 2, 3, .., 9. (b) Draw the depth-first search tree (or forest). Give the discovery time and finishing time of each vertex. (c) Does there exist a topological ordering for the graph? If yes, given an ordering. If no, justify