...
GATE 1991
November 25, 2023
UGC NET CS 2018-DEC Paper-2
November 26, 2023
GATE 1991
November 25, 2023
UGC NET CS 2018-DEC Paper-2
November 26, 2023

Question 3739 – Algorithms

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?

Correct Answer: A

Question 270 Explanation: 
A DFS starting at some vertex ‘v’ explores the graph by building up a tree that contains all vertices that are reachable from ‘v’ and all edges that are used to reach these vertices. We call this tree a DFS tree. A complete DFS exploring the full graph (and not only the part
reachable from a given vertex ‘v’) builds up a collection of trees, or forest, called a DFS forest.
Based on definition of DFS forest, option-A is correct.
A
{a, b, e} {c, d, f, g, h}
B
{a, b, e} {c, d, h} {f, g}
C
{a, b, e} {f, g} {c, d} {h}
D
{a, b, c, d} {e, f, g} {h}
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x