Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged depth-first-search
1
votes
1
answer
31
How does below property hold for cross edge in a DFS Tree ?
If (u,v) is a cross edge then start[u] > start[v] end[u] > end[v]
If (u,v) is a cross edge thenstart[u] start[v]end[u] end[v]
radha gogia
855
views
radha gogia
asked
Aug 20, 2018
Algorithms
algorithms
depth-first-search
+
–
0
votes
2
answers
32
Test Datasructures
Statement I : If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge Statement II : A graph G has a cycle if DFS finds at least 1 Backedge Which of the following option is correct ? ... option is correct(Statement 1 is false and Statement 2 is true but answer given is 1, please tell me where i am making mistake.
Statement I : If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 BackedgeStatement II : A graph G has a cycle ...
Prince Sindhiya
257
views
Prince Sindhiya
asked
Aug 11, 2018
Algorithms
depth-first-search
graph-theory
data-structures
+
–
0
votes
0
answers
33
DFS BFS
Please give an example i didn't get it The depth of any DFS tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex.
Please give an example i didn't get itThe depth of any DFS tree rooted at a vertex is at least as much as thedepth of any BFS tree rooted at the same vertex.
Rishav Kumar Singh
765
views
Rishav Kumar Singh
asked
Aug 2, 2018
Algorithms
depth-first-search
breadth-first-search
algorithms
+
–
0
votes
0
answers
34
DFS algorithms
state TRUE or FALSE. and why Running a DFS on an undirected graph G = (V;E) always produces the same number of cross edges, no matter what order the vertex list V is in and no matter what order the adjacency lists for each vertex are in.
state TRUE or FALSE. and whyRunning a DFS on an undirected graph G = (V;E) always produces the samenumber of cross edges, no matter what order the vertex list V is in and...
Rishav Kumar Singh
776
views
Rishav Kumar Singh
asked
Aug 2, 2018
Algorithms
depth-first-search
graph-algorithm
+
–
3
votes
1
answer
35
DFS Algo
Is following statement true/false? A DFS of a directed graph always produces the same number of tree edges, i.e., independent of the order in which vertices are considered for DFS. Answer is FALSE please explain
Is following statement true/false? A DFS of a directed graph always produces the same number of tree edges, i.e., independent of the order in which vertices are considere...
Rishav Kumar Singh
2.0k
views
Rishav Kumar Singh
asked
Jul 30, 2018
Algorithms
depth-first-search
algorithms
+
–
5
votes
1
answer
36
#Algorithms #DFS
Consider the tree arcs of a $DFS$ traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing the shortest path between every pair of vertices. the shortest path from $W$ ... in the graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.
Consider the tree arcs of a $DFS$ traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure...
iarnav
1.0k
views
iarnav
asked
May 28, 2018
Algorithms
algorithms
graph-algorithm
depth-first-search
+
–
0
votes
0
answers
37
#Algorithms #DFS How to find if a directed graph G is strongly connected using DFS in one pass?
I know, Kosaraju algorithm and there's one other algorithm which involves reversing of G and using DFS, but two times, but there's some algorithm which uses DFS only time, but I can't be able find that algorithm. Someone please share that.
I know, Kosaraju algorithm and there's one other algorithm which involves reversing of G and using DFS, but two times, but there's some algorithm which uses DFS only time...
iarnav
408
views
iarnav
asked
May 13, 2018
Algorithms
graph-theory
algorithms
depth-first-search
graph-algorithm
+
–
1
votes
4
answers
38
algorithm
In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as x/yx/y, where x is discovery time stamp and y is finishing time stamp It shows which of the following depth first forest? {a,b,e} {c,d,f,g,h} {a,b,e} {c,d,h} {f,g} {a,b,e} {f,g} {c,d} {h} {a,b,c,d} {e,f,g} {h}
In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as x/yx/y, where x is discovery time stamp and y is finishin...
eyeamgj
2.3k
views
eyeamgj
asked
May 10, 2018
Algorithms
depth-first-search
graph-algorithm
graph-search
+
–
0
votes
0
answers
39
DFS Modification
How DFS(Depth First Search) modification is used to find whether a graph is planar or not ?
How DFS(Depth First Search) modification is used to find whether a graph is planar or not ?
ankitgupta.1729
1.3k
views
ankitgupta.1729
asked
Mar 21, 2018
Algorithms
depth-first-search
algorithms
graph-algorithm
shai-simonson
+
–
0
votes
0
answers
40
DFS-Algorithm
Let T be a depth first search tree in an undirected graph G. Vertices u and ν are leaves of this tree T. The degrees of both u and ν in G are at least 2. In such case in the graph there will be two cycles :- One Cycle will contain u and other one v. There cannot be a graph containig a single cycle and containing both u and v and also satisfy above Constraint. Am I right?
Let T be a depth first search tree in an undirected graph G. Vertices u and ν are leaves of this tree T. The degrees of both u and ν in G are at least 2.In such case in...
Na462
809
views
Na462
asked
Feb 18, 2018
Algorithms
depth-first-search
algorithms
graph-algorithm
+
–
6
votes
1
answer
41
Back edge,tree edge,forward edges in BFS
Consider the following statements: 1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff it has at least two children. 2. When BFS is carried out on a directed ... back edge, or cross edge and not forward edge as in the case of DFS. Find TRUE or FALSE for both the statements
Consider the following statements:1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff i...
MIRIYALA JEEVAN KUMA
13.2k
views
MIRIYALA JEEVAN KUMA
asked
Jan 27, 2018
DS
algorithms
breadth-first-search
depth-first-search
graph-algorithm
programming-in-c
data-structures
+
–
4
votes
1
answer
42
DFS- depth first search
budhu
702
views
budhu
asked
Jan 25, 2018
DS
data-structures
depth-first-search
graph-algorithm
graph-connectivity
+
–
2
votes
0
answers
43
DFS- Depth First Search
If we backtrack in DFS ,then doesn't statement 1 becomes true ?
If we backtrack in DFS ,then doesn't statement 1 becomes true ?
Pawan Kumar 2
468
views
Pawan Kumar 2
asked
Jan 13, 2018
Graph Theory
depth-first-search
+
–
2
votes
2
answers
44
DFS Traversal
If DFS algorithm applied starting from vertex ‘A’ which uses stack data structure then the height of stack is needed in worst case for DFS traversal is _________.
If DFS algorithm applied starting from vertex ‘A’ which uses stack data structure then the height of stack is needed in worst case for DFS traversal is _________.
sumit chakraborty
1.2k
views
sumit chakraborty
asked
Jan 11, 2018
Algorithms
depth-first-search
algorithms
graph-algorithm
numerical-answers
made-easy-test-series
+
–
2
votes
1
answer
45
Ace testseries
How TO SOLVE?
How TO SOLVE?
rasto mapp
229
views
rasto mapp
asked
Jan 10, 2018
Algorithms
algorithms
depth-first-search
ace-test-series
+
–
1
votes
0
answers
46
Test Series
Choose the correct option, from the following: I) We can find the cycle in the graph using BFS. II) We can find the cycle in the graph using DFS. III)Both Correct IV)Both wrong
Choose the correct option, from the following:I) We can find the cycle in the graph using BFS.II) We can find the cycle in the graph using DFS.III)Both CorrectIV)Both wro...
ankit_thawal
393
views
ankit_thawal
asked
Jan 10, 2018
Programming in C
depth-first-search
cycle
+
–
1
votes
1
answer
47
Depth First Search
Aditya Bahuguna
637
views
Aditya Bahuguna
asked
Jan 7, 2018
Algorithms
graph-algorithm
depth-first-search
test-series
+
–
0
votes
0
answers
48
made easy test series
rohit vishkarma
697
views
rohit vishkarma
asked
Jan 4, 2018
Algorithms
graph-
depth-first-search
+
–
1
votes
1
answer
49
DFS- Depth First Search
Shubham Kumar Gupta
1.1k
views
Shubham Kumar Gupta
asked
Dec 3, 2017
Algorithms
depth-first-search
algorithms
graph-algorithm
data-structures
test-series
+
–
1
votes
1
answer
50
Madeasy 2k17
Caption
Caption
kamakshi
1.3k
views
kamakshi
asked
Nov 18, 2017
Algorithms
graph-algorithm
topological-sort
depth-first-search
made-easy-test-series
+
–
1
votes
2
answers
51
DFS , how to slove it?
Parshu gate
1.4k
views
Parshu gate
asked
Nov 18, 2017
DS
depth-first-search
algorithms
graph-algorithm
+
–
6
votes
1
answer
52
Algo doubt
Which of the following is false? 1)An edge(u,v) is forward edge if and only if d[u] < =d[v] <= f[v] <= f[u]. 2) an edge (u,v) is a cross edge if and only if d[u] < f[u] < d[v] < f[v]. 3) an edge (u,v) is a back edge if and only if d[v] < d[u] < f[u] < f[v].
Which of the following is false?1)An edge(u,v) is forward edge if and only ifd[u] < =d[v] <= f[v] <= f[u].2) an edge (u,v) is a cross edge if and only ifd[u] < f[u] < d[v...
Surya Dhanraj
1.3k
views
Surya Dhanraj
asked
Nov 8, 2017
Algorithms
depth-first-search
tree
+
–
0
votes
0
answers
53
techtud
Let G is a graph with n vertices and m edges. Consider following statements : i. In DFS traversal, number of tree edges produced is independent of selection of starting vertex. ii. In BFS traversal, number of tree edges produced is independent of selection of starting vertex. iii. ... B) Only statements (ii) and (iii) are correct (C) Statements (ii) and (iv) both are wrong (D) None of these
Let G is a graph with n vertices and m edges. Consider following statements : i. In DFS traversal, number of tree edges produced is independent of selection of starting v...
Manoja Rajalakshmi A
630
views
Manoja Rajalakshmi A
asked
Nov 7, 2017
Computer Networks
computer-networks
depth-first-search
breadth-first-search
+
–
1
votes
1
answer
54
Depth first search
Consider the following graph G. Modified DFS on G applied as follows: • Starting vertex is ‘p’. • Vertex is visited based on alphabetic order. • Vertices are visited in order p, q, r, s, t, v. • It works same as DFS except the visiting order restriction What is the number of back edges during the above DFS traversal on G ______________
Consider the following graph G.Modified DFS on G applied as follows:• Starting vertex is ‘p’.• Vertex is visited based on alphabetic order.• Vertices are visite...
shivangi5
1.5k
views
shivangi5
asked
Nov 6, 2017
Algorithms
depth-first-search
+
–
0
votes
0
answers
55
Single source softest path via DFS
Hi Guys, BFS could be used for finding single source shortest path in unweighted graph. But could we use DFS also ? Please share your valuable opinion. PS: I think after little bit modification DFS could also be used but it's running time will increase.
Hi Guys,BFS could be used for finding single source shortest path in unweighted graph. But could we use DFS also ? Please share your valuable opinion.PS: I think after li...
Chhotu
302
views
Chhotu
asked
Nov 4, 2017
Algorithms
graph-algorithm
algorithms
depth-first-search
+
–
0
votes
1
answer
56
Depth First Search
Please someone explain .... A directed graph G is acyclic iff depth first search of G yields no back edges
Please someone explain ....A directed graph G is acyclic iff depth first search of G yields no back edges
Shivi rao
574
views
Shivi rao
asked
Oct 31, 2017
Programming in C
depth-first-search
+
–
0
votes
1
answer
57
DFS: Practice Exercise
Q1. Consider the following DFS algorithm for cycle detection in a graph. DFS(G) for each vertex u Belongs G.V u.color = WHITE U.pi = NIL time = 0 for each vertex u Belongs G.V if u.color == WHITE DFS-VISIT(G , u) DFS-VISIT(G, u) time = ... DFS tree if we draw an edge from one leaf node to another leaf node then that edge is called cross edge. Is this statement is true ??
Q1. Consider the following DFS algorithm for cycle detection in a graph.DFS(G) for each vertex u Belongs G.V u.color = WHITE U.pi = NIL time = 0 for each vertex u Belongs...
Shubhanshu
544
views
Shubhanshu
asked
Oct 28, 2017
Algorithms
algorithms
graph-algorithms
depth-first-search
+
–
3
votes
0
answers
58
DFS: certain nodes not pushed to the stack.
Which of the following are true:- 1. DFS continues to visited first unvisited successor of each node as long as possible. 2. Certain nodes are pushed into the stack. 3. DFS first visits all the immediate successors of a node before moving to their ... nodes are pushed into the stack. 3. False -- this happens in BFS not in DFS. 4. True -- Iterative DFS.
Which of the following are true:-1. DFS continues to visited first unvisited successor of each node as long as possible.2. Certain nodes are pushed into the stack.3. DFS ...
Shubhanshu
712
views
Shubhanshu
asked
Oct 20, 2017
Algorithms
algorithms
depth-first-search
graph-algorithms
data-structures
+
–
2
votes
0
answers
59
DFS: number of nodes not pushed into the stack.
I have seen these following question:- Number of Vertices pushed more than once. https://gateoverflow.in/5296/number-of-vs-that-are-pushed-more-than-once-in-a-dfs https://gateoverflow.in/98484/dfs-using-stack Vertices not pushed ... and every vertex pushed exactly once into the stack http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/.
I have seen these following question:-Number of Vertices pushed more than once.https://gateoverflow.in/5296/number-of-vs-that-are-pushed-more-than-once-in-a-dfshttps://ga...
Shubhanshu
2.0k
views
Shubhanshu
asked
Oct 18, 2017
DS
data-structures
stack
depth-first-search
+
–
0
votes
0
answers
60
Depth first search
What is the correct answer please provide with reason?
What is the correct answer please provide with reason?
saumya mishra
279
views
saumya mishra
asked
Sep 25, 2017
Algorithms
depth-first-search
data-structures
graph-algorithms
+
–
Page:
« prev
1
2
3
4
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register