Dark Mode

Recent questions tagged depth-first-search

0 votes

1 answer

91

Why is the below expression correct for a cross edge in case of DFS ?
Cross Edge(a,b) is defined as an edge between two non-ancestor nodes in DFS , so my query is that how is this stmt true : arrival[b] <departure[b] <arrival[a] <departure[a] ...

radha gogia asked in Algorithms Jul 5, 2015

488 views

0 votes

2 answers

92

Does a DFS produce same no of tree edges in an undirected graph ?
Does a DFS for an undirected graph always produce the same number of tree edges irrespective of the order in which we visit the vertices ?

radha gogia asked in Algorithms Jun 30, 2015

1.8k views

1 vote

2 answers

93

Which of the following statement is correct regarding DFS?
Which of the following statement is correct regarding DFS? 1) All the vertices are pushed in the stack during DFS Traversal. 2) No vertex is pushed more than once in the stack during traversal.

Gate Aspirant 2 asked in Algorithms Dec 19, 2014

by Gate Aspirant 2

2.5k views

29 votes

8 answers

94

GATE IT 2006 | Question: 47
Consider the depth-first-search of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is first visited, and finish time $f(u)$ represent the time instant when the ... are two connected components, and $Q$ and $R$ are connected There are two connected components, and $P$ and $Q$ are connected

Ishrat Jahan asked in Algorithms Oct 31, 2014

by Ishrat Jahan

11.1k views

52 votes

11 answers

95

GATE IT 2007 | Question: 24
A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which the DFS call to the vertex $u$ terminates. Which of the following statements is always TRUE for all edges $(u, v)$ in the graph ? $d[u] < d[v]$ $d[u] < f[v]$ $f[u] < f[v]$ $f[u] > f[v]$

Ishrat Jahan asked in Algorithms Oct 29, 2014

by Ishrat Jahan

13.6k views

23 votes

3 answers

96

GATE IT 2008 | Question: 47
Consider the following sequence of nodes for the undirected graph given below: $a$ $b$ $e$ $f$ $d$ $g$ $c$ $a$ $b$ $e$ $f$ $c$ $g$ $d$ $a$ $d$ $g$ $e$ $b$ $c$ $f$ $a$ $d$ $b$ $c$ $g$ $e$ $f$ A Depth First Search (DFS) is started at ... first visited. Which of the above is/are possible output(s)? $1$ and $3$ only $2$ and $3$ only $2, 3$ and $4$ only $1, 2$ and $3$ only

Ishrat Jahan asked in Algorithms Oct 28, 2014

by Ishrat Jahan

7.8k views

Page:

« prev
1
2
3
4

Recent questions tagged depth-first-search