Question

Figure 1: Graph for Problem 1 Problem 1 Consider a depth-first search on the graph shown in Figure 1, starting with node c. Consider a node to be "visited" whenever there is a call to dfs with the node as the second argument a) Which nodes are visited, and in what order? Use the convention that graph.neighbors ) produces successors in ascending order of label b) Suppose you call dfs_times (graph, 'c') on the graph above. This function returns dictionaries times.start and times.finish. Write down the contents of these dictionaries as they are when the function exits

Answer 1

a) Order of Nodes visited : C B D E G H F A

Starting with node C [C], node C has two neighbors node B and node F. As per the function of graph.neighbors() node B will be visited first [C-B] and then node F will be visited after visiting the neighbors of node B. After visiting B, node D [C-B-D] will be visited as it is the only neighbor of node B. D has two neighbors E and F (F will be visited after visiting E and its neighbors) [C-B-D-E-G-H-F]. Now, only node A is remaining because it is not reachable from any other node. So, it will be visited at last [C-B-D-E-G-H-F-A].

B) time .start/time finish are mentioned in the figure given below.

Explanation: same as part a)

2/13 3/12 10/1 1/14 5/8 15/16 4/9