recategorized by
7,599 views
6 votes
6 votes

In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as $x/y$, where $x$ is discovery time stamp and $y$ is finishing time stamp.

It shows which of the following depth first forest?

  1. {a,b,e} {c,d,f,g,h}
  2. {a,b,e} {c,d,h} {f,g}
  3. {a,b,e} {f,g} {c,d} {h}
  4. {a,b,c,d} {e,f,g} {h}
recategorized by

2 Answers

6 votes
6 votes

Look at the image above different transition diagrams are drawn for DFS traversal on the given graph. As the edges are explored by the algorithm they are shown red in colour and green when the edges are backtraced. New discovered vertices are black in colour and after finishing they are coloured yellow. So, the tree vertices are yellow in colour and the edges are green in colour.

EXPLANATION OF THE ABOVE FIGURES

Figure 1 : Starting the DFS traversal with vertex C [ Since the discovery time of C in the question is 1 ]

Figure 2 : Traversing the edge cg the vertex g is discovered and time stamped as 2

[which matches with the discovery time of g in the question]

Figure 3: Vertex f is discovered through the edge gf and time stamped as 3 [ which matches with the discovery time of f in the question]

Figure 4: Nowhere to go from f so we are backtracing to g. So, the finishing time of f becomes 4 [ which matches with the question]

Figure 5: From g we are going to h. So, the vertex h is discovered through the edge gh.Thus the discovery time of h is 5.[ which matches with the question]

Figure 6: Doing two steps at a time back tracing from h to g and then g to c. thus the finishing time of h and g becomes 6 and 7 respectively. [ which matches with the question]

Figure 7: From c vertex d is discovered through cd. Thus the discovery time of d is 8. [ which matches with the question]

Figure 8 : From d back tracing to c and no where to go from c so the finishing time of d and c becomes 9 and 10 respectively. Thus the tree {c,d,f,g,h} is formed. [ which matches with the question]

Figure 9: Starting a new dfs traversal from b. The vertices e and a are discovered through be and ea.Thus the discovery times of b,e,a are 11,12,13. [ which matches with the question]

Figure 10 Back tracing from a to e and then to b. Thus the finishing times of a,e and b becomes 14,15 and 16 respectively and the tree {a,b,e} is formed. [ which matches with the question]

So, our DFS forest is {a,b,e} { c,d,f,g,h} .

Hence Option A is correct. 

Answer:

Related questions

2 votes
2 votes
3 answers
1
go_editor asked Aug 8, 2016
2,186 views
An ideal sort is an in-place-sort whose additional space requirement isO (log$_2$ n)O (nlog$_2$ n)O (1)O (n)
3 votes
3 votes
1 answer
2
go_editor asked Aug 8, 2016
3,019 views
The number of disk pages access in B-tree search, where h is height, n is the number of keys and t is the minimum degree, is$\theta (\log_n h*t)$$\theta (\log_t n*h)$$\th...
1 votes
1 votes
2 answers
3
6 votes
6 votes
2 answers
4
go_editor asked Aug 8, 2016
3,468 views
How many solutions are there for the equation $x+y+z+u=29$ subject to the constraints that $x \geq 1, \: \: y \geq 2 \: \: z \geq 3 \: \: and \: \: u \geq 0$?496026002375...