The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged dfs
0
votes
0
answers
1
BFS and DFS  types of edges
Can someone please explain what are the types of edges possible in BFS and DFS for DIRECTED as well as UNDIRECTED graphs? Individual meaning of BACK, FRONT and CROSS edges is clear, but can’t decide which are present and which are not for Traversals. an example would be of great help or any specific reference on this.
asked
Dec 30, 2018
in
Algorithms
by
Markzuck
Junior
(
633
points)

53
views
dfs
bfs
algorithms
graphalgorithms
0
votes
1
answer
2
BFS problem
True or False , with reason. For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic? Answer is False Explanation: FALSE. It is true that the absence of back edges with respect to a DFS tree ... a cycle using such cross edges (which decrease the level) and using forward edges (which increase the level) Can someone explain it ?
asked
Dec 25, 2018
in
Algorithms
by
Sandy Sharma
Active
(
1.3k
points)

105
views
algorithms
graphalgorithms
dfs
datastructure
bfs
+1
vote
1
answer
3
Which of the following condition is sufficient to detect cycle in a directed graph?
asked
Dec 12, 2018
in
Algorithms
by
Gangani_Son
(
163
points)

174
views
graphtheory
dfs
geekstogeeks
graphalgorithms
0
votes
1
answer
4
which DFS algorithm to follow?
there are multiple algorithm of DFS available and i cant figure out which one to follow for solving question asking for the nodes which aren't pushed into the stack or the nodes which are pushed more than once, Tried to figure out from ... , https://gateoverflow.in/98484/dfsusingstack https://gateoverflow.in/161225/dfsnumberofnodesnotpushedintothestack
asked
Dec 9, 2018
in
Algorithms
by
Shivam Kasat
Active
(
1.9k
points)

55
views
dfs
algorithms
graphalgorithms
+1
vote
0
answers
5
Depth First Search: Finding if The graph is connected
Better Explanation??
asked
Dec 8, 2018
in
DS
by
pradeepchaudhary
Active
(
1.1k
points)

32
views
datastructure
dfs
graphalgorithms
+1
vote
0
answers
6
Algorithm Back Edges
Does Back Edges in both BFS and DFS leads to cycle in a directed graph? Please elaborate.
asked
Nov 26, 2018
in
Algorithms
by
Shamim Ahmed
Active
(
2.3k
points)

54
views
algorithms
bfs
dfs
0
votes
0
answers
7
Graph Search
Which of the following statements are True$?$ $(1)$ In a depthfirst search of an undirected graph $G,$every edge of $G$ is either a tree edge or a back edge$.$ $(2)$ Forward and cross edges never occur in a depthfirst search of an undirected graph$.$ $(3)$ A directed graph is ... first search yields no back edges$.$ $A)1$ $B)1$ $and$ $2$ $C)2$ $and$ $3$ $D)$ $All$ $of$ $these$
asked
Nov 13, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
29.4k
points)

28
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
8
Depth First Search (DFS)
Consider the following sequence of nodes for the undirected graph given below$:$ $(1)PQSTWVUR$ $(2)PQRSTUWV$ $(3)PQRTUSVW$ A Depth First Search (DFS) is started at node $P.$The nodes are listed in the order they are first visited. Which all of the above are possible outputs$?$ $A)Only (2)$ $B)(1) and (2)$ $C)(2) and (3)$ $D)(1) and (2)$
asked
Nov 13, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
29.4k
points)

50
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
9
Depth First Search
asked
Nov 7, 2018
in
Programming
by
Na462
Loyal
(
8.7k
points)

158
views
dfs
datastructure
graphalgorithms
–1
vote
0
answers
10
DFS (explain)
asked
Sep 24, 2018
in
DS
by
balaganesh
(
145
points)

29
views
dfs
0
votes
0
answers
11
DFS Tree
Consider the tree arcs of a DFS traversal from a source node W in an unweighted, connected, undirected, acyclic graph. The tree T formed by the tree arcs is a data structure for computing 1. the shortest path between every pair of vertices. 2. the shortest path from W ... the graph. 3. the shortest paths from W to only those nodes that are leaves of T. 4. the longest path in the graph.
asked
Sep 1, 2018
in
Algorithms
by
K ANKITH KUMAR
(
209
points)

76
views
dfs
algorithms
graphalgorithms
0
votes
0
answers
12
DFSArticulation Point and Bridges
I want to find the articulation point and bridges in the above graph. Further for each vertex $v$ I want to compute $v.low=$min $\left \{ v.d, w.d \right \}$ where $v.d$=discovery time of vertex v $w.d$=discovery time of ... someone help me with the values of v.low ? Because based on v.low I will be further able to solve articulation point and bridge problem.
asked
Aug 28, 2018
in
DS
by
Ayush Upadhyaya
Boss
(
24.9k
points)

44
views
graph
dfs
algorithms
0
votes
1
answer
13
Topological ordering and DFS
If we apply Topological and DFS traversal. Is there any intersection of ordering? Please explain.
asked
Aug 26, 2018
in
Algorithms
by
Rishav Kumar Singh
Loyal
(
5.5k
points)

75
views
topologicalsort
dfs
+2
votes
0
answers
14
Depth first search
The maximum number of edges possible with UDG of n nodes,when DFS call on any random node in the graph result in stack size of 5. i.e. 5 function calls present in stack simultaneously are ......... Ans. 10
asked
Aug 21, 2018
in
DS
by
Na462
Loyal
(
8.7k
points)

102
views
dfs
datastructure
graphalgorithms
+1
vote
2
answers
15
Test Datastructure
We are provided with an undirected connected graph such that weight of all the edges is equal to some constant k. We wish to find the shortest distance between given pair of nodes. Which of the following statements is(are) true? I. We can use Depth First Search to ... correct result only if the given graph is a tree. Only I and II Only II and IV Only III and IV Only II and III
asked
Aug 11, 2018
in
Algorithms
by
Prince Sindhiya
Loyal
(
6.2k
points)

76
views
dfs
bfs
0
votes
0
answers
16
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.
asked
Aug 2, 2018
in
Algorithms
by
Rishav Kumar Singh
Loyal
(
5.5k
points)

53
views
dfs
bfs
algorithms
0
votes
0
answers
17
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.
asked
Aug 2, 2018
in
Algorithms
by
Rishav Kumar Singh
Loyal
(
5.5k
points)

27
views
dfs
graphalgorithms
+3
votes
1
answer
18
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
asked
Jul 30, 2018
in
Algorithms
by
Rishav Kumar Singh
Loyal
(
5.5k
points)

39
views
dfs
algorithms
+2
votes
1
answer
19
#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.
asked
May 28, 2018
in
Algorithms
by
iarnav
Loyal
(
9.6k
points)

152
views
algorithms
graphalgorithms
graphtheory
dfs
0
votes
0
answers
20
#Algorithms #DFS How to find if a directed graph G is strongly connected using DFS in one pass?
asked
May 13, 2018
in
Algorithms
by
iarnav
Loyal
(
9.6k
points)

84
views
graphtheory
algorithms
dfs
graphalgorithms
0
votes
1
answer
21
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 ________? Soln. Its a simple piece of cake we just need to find that path which leads to maximum nodes ... 0 and when to start counting with 1 because such type of ambiguous question always let my question go wrong and its painful :(
asked
May 6, 2018
in
Algorithms
by
Na462
Loyal
(
8.7k
points)

108
views
dfs
algorithms
graphalgorithms
0
votes
0
answers
22
DFS Modification
How DFS(Depth First Search) modification is used to find whether a graph is planar or not ?
asked
Mar 21, 2018
in
Algorithms
by
ankitgupta.1729
Loyal
(
10k
points)

175
views
dfs
algorithms
graphalgorithms
shaisimonson
0
votes
0
answers
23
DFSAlgorithm
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?
asked
Feb 18, 2018
in
Algorithms
by
Na462
Loyal
(
8.7k
points)

153
views
dfs
algorithms
graphalgorithms
+5
votes
1
answer
24
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
asked
Jan 27, 2018
in
DS
by
MIRIYALA JEEVAN KUMA
Active
(
2.4k
points)

1.1k
views
algorithms
bfs
dfs
graphalgorithms
programminginc
datastructure
+2
votes
0
answers
25
DFS depth first search
asked
Jan 25, 2018
in
DS
by
budhu
(
159
points)

93
views
datastructure
dfs
graphalgorithms
graphconnectivity
+2
votes
0
answers
26
DFS Depth First Search
If we backtrack in DFS ,then doesn't statement 1 becomes true ?
asked
Jan 13, 2018
in
Graph Theory
by
Pawan Kumar 2
Active
(
4.7k
points)

73
views
dfs
+2
votes
1
answer
27
Ace testseries
How TO SOLVE?
asked
Jan 10, 2018
in
Algorithms
by
Deepak Mokili
(
307
points)

53
views
algorithms
dfs
+1
vote
0
answers
28
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
asked
Jan 10, 2018
in
Programming
by
ankit_thawal
Active
(
2.1k
points)

60
views
dfs
cycle
0
votes
0
answers
29
made easy test series
asked
Jan 4, 2018
in
Algorithms
by
rohit vishkarma
Junior
(
989
points)

144
views
graph
dfs
+1
vote
1
answer
30
ace test series
asked
Dec 27, 2017
in
Algorithms
by
rohit vishkarma
Junior
(
989
points)

60
views
dfs
Page:
1
2
3
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Important Dates for Counselling (GATE 2019)
IIT Gandhinagar review
AIR175 : GO is enough
GATE 2019 My reasoned routine. (AIR 558)
if i can you also can
Follow @csegate
Recent questions tagged dfs
Recent Blog Comments
not yet..
Has IIT Hyderabad admission opened? Not able to...
Congratulations on your achievement. Can you...
It's nice one. Not that technically difficult...
48,725
questions
52,831
answers
183,520
comments
68,659
users