The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
Recent questions tagged dfs
+1
vote
1
answer
1
CLRS Chapter22 Figure22.6
What are the strongly connected components in the above figure ?
asked
Mar 30, 2019
in
Algorithms
by
Doraemon
Junior
(
821
points)

76
views
stronglyconnectedcomponents
dfs
graphalgorithms
0
votes
0
answers
2
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
(
675
points)

300
views
dfs
bfs
algorithms
graphalgorithms
0
votes
1
answer
3
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.2k
points)

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

447
views
graphtheory
dfs
geekstogeeks
graphalgorithms
0
votes
1
answer
5
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
(
3.2k
points)

146
views
dfs
algorithms
graphalgorithms
+1
vote
1
answer
6
Depth First Search: Finding if The graph is connected
Better Explanation??
asked
Dec 8, 2018
in
DS
by
pradeepchaudhary
Active
(
1.3k
points)

62
views
datastructures
dfs
graphalgorithms
+1
vote
0
answers
7
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.5k
points)

92
views
algorithms
bfs
dfs
0
votes
1
answer
8
Graph Search
Which of the following statements are true? In a depthfirst search of an undirected graph $G,$every edge of $G$ is either a tree edge or a back edge Forward and cross edges never occur in a depthfirst search of an undirected graph A directed graph is acyclic if and only if a depthfirst search yields no back edges $1$ $1$ and $2$ $2$ and $3$ All of these
asked
Nov 13, 2018
in
Algorithms
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

86
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
9
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
Veteran
(
60.8k
points)

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

195
views
dfs
datastructures
graphalgorithms
+4
votes
1
answer
11
Graph
Also let me know the approach to find back edges, cross edges, forward edges, How to solve these questions
asked
Sep 15, 2018
in
Algorithms
by
manvi_agarwal
(
111
points)

455
views
algorithms
graphalgorithms
dfs
descriptive
0
votes
0
answers
12
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
(
207
points)

116
views
dfs
algorithms
graphalgorithms
0
votes
1
answer
13
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
(
30.6k
points)

72
views
graph
dfs
algorithms
0
votes
1
answer
14
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.7k
points)

123
views
topologicalsort
dfs
+2
votes
0
answers
15
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
(
7.1k
points)

181
views
dfs
datastructures
graphalgorithms
+1
vote
2
answers
16
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
(
5.9k
points)

110
views
dfs
bfs
0
votes
0
answers
17
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.7k
points)

122
views
dfs
bfs
algorithms
0
votes
0
answers
18
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.7k
points)

46
views
dfs
graphalgorithms
+3
votes
1
answer
19
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.7k
points)

70
views
dfs
algorithms
+3
votes
1
answer
20
#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
(
8.5k
points)

235
views
algorithms
graphalgorithms
graphtheory
dfs
0
votes
0
answers
21
#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
(
8.5k
points)

120
views
graphtheory
algorithms
dfs
graphalgorithms
0
votes
1
answer
22
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
(
7.1k
points)

204
views
dfs
algorithms
graphalgorithms
0
votes
0
answers
23
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
Boss
(
17.6k
points)

273
views
dfs
algorithms
graphalgorithms
shaisimonson
0
votes
0
answers
24
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
(
7.1k
points)

191
views
dfs
algorithms
graphalgorithms
+6
votes
1
answer
25
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)

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

122
views
datastructures
dfs
graphalgorithms
graphconnectivity
+2
votes
0
answers
27
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.2k
points)

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

62
views
algorithms
dfs
+1
vote
0
answers
29
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
(
1.4k
points)

82
views
dfs
cycle
0
votes
0
answers
30
made easy test series
asked
Jan 4, 2018
in
Algorithms
by
rohit vishkarma
Active
(
1.1k
points)

205
views
graph
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
PSUs Recruitment
ISRO Recruitment
BARC Recruitment
GATE CSE: All NITs Admissions
GATE CSE: IIT Hyderabad Admissions
Follow @csegate
Recent questions tagged dfs
Recent Blog Comments
next level blog ..thanks
CIL question is far better. (ambiguity...
yes.... coal india framed the question paper than...
Coal india framed questions far better than...
Congratulations ....
50,834
questions
57,838
answers
199,510
comments
108,346
users