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 bfs
0
votes
0
answers
1
Cormen Edition 3 Exercise 22.2 Question 8 (Page No. 539)
The diameter of a tree $T= (V, E)$ is defined as $max_{u,v\ \epsilon\ V}\ \delta(u,v)$, that is, the largest of all shortestpath distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.
asked
Nov 12
in
Algorithms
by
Kushagra गुप्ता
Active
(
1.8k
points)

66
views
cormen
graphalgorithms
bfs
descriptive
0
votes
0
answers
2
Cormen Edition 3 Exercise 22.2 Question 7 (Page No. 539)
There are two types of professional wrestlers: babyfaces ( good guys ) and heels ( bad guys ). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we ... between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it.
asked
Nov 12
in
Algorithms
by
Kushagra गुप्ता
Active
(
1.8k
points)

24
views
cormen
graphalgorithms
bfs
descriptive
0
votes
0
answers
3
Cormen Edition 3 Exercise 22.2 Question 6 (Page No. 539)
Give an example of a directed graph $G=(V, E)$, a source vertex $s\ \epsilon\ V$ , and a set of tree edges $E_{\Pi}\subseteq E$ such that for each vertex $v\ \epsilon\ V$ ... set of edges $E_{\Pi}$ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.
asked
Nov 12
in
Algorithms
by
Kushagra गुप्ता
Active
(
1.8k
points)

15
views
cormen
bfs
graphalgorithms
descriptive
+1
vote
1
answer
4
BFS traversal path
What will be the path from AH if BFS is used in the following graph?
asked
Feb 2
in
Algorithms
by
saptarshiDey
(
117
points)

93
views
graphalgorithms
algorithms
bfs
datastructure
0
votes
0
answers
5
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
(
667
points)

181
views
dfs
bfs
algorithms
graphalgorithms
0
votes
1
answer
6
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)

159
views
algorithms
graphalgorithms
dfs
datastructure
bfs
+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.4k
points)

80
views
algorithms
bfs
dfs
0
votes
0
answers
8
EdgeClassification In DIrected Graph using BFS
In BFS of a directed graph, we don't have forward edges.Only tree edge,cross edge or back edge. Below is a sample graph I have taken and classified edge types. Please verify guys whether it's correct. The ... in the selected answer here. https://stackoverflow.com/questions/29631211/edgeclassificationduringbreadthfirstsearchonadirectedgraph
asked
Nov 22, 2018
in
Programming
by
Ayush Upadhyaya
Boss
(
27.6k
points)

289
views
graphalgorithms
bfs
0
votes
0
answers
9
BFS TRAVERSAL
HOW CAN WE GET A CROSS EDGE WHILE PERFORMING A BFS ON UNDIRECTED AND DIRECTED GRAPH CAN ANYONE SHOW WITH AN EXAMPLE?
asked
Nov 21, 2018
in
Programming
by
codingo1234
Junior
(
861
points)

50
views
bfs
algorithms
graphalgorithms
0
votes
0
answers
10
Breadth First Search(BFS)
$01$ $BFS$ (Breadth First Search)al is used to find the shortest distance between two nodes in a graph provided that the edges in the graph have the weights $0$ or $1.$Which of the following data structure is most efficient in traversing a graph by $01$ $BFS?$ $A)$ Priority queue $B)$Stack $C)$ Doubleended queue $D)$ Linked list
asked
Nov 13, 2018
in
Algorithms
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

84
views
algorithms
graphalgorithms
bfs
0
votes
1
answer
11
BFS Traversal
Maximum number of BFS Traversal Possible on BST of height 3 is ..........
asked
Oct 21, 2018
in
Programming
by
Na462
Loyal
(
6.9k
points)

93
views
bfs
algorithms
datastructure
+2
votes
1
answer
12
general doubt on breadth first search
While doing BFS , at any time in queue suppose there are r vertices v1,v2,v3.....vr with v.d as the distance from the source. Then according to me at any time in a queue, v1.d=v2.d or v2.d=v1.d+1 But in cormen its written that v2.d<=v1.d+1 Can someone please explain?
asked
Oct 3, 2018
in
DS
by
sushmita
Boss
(
17.2k
points)

98
views
bfs
datastructure
graphalgorithms
0
votes
0
answers
13
back edge and no forward edge
Which does this sentence mean? In BFS of an undirected graph, there are no back edge and no forward edge.
asked
Aug 23, 2018
in
DS
by
syncronizing
Junior
(
815
points)

260
views
programminginc
datastructure
bfs
+4
votes
0
answers
14
Breadth first Search
Which of following statement is true ? A. In BFS of UDG there are no back edges and forward edges. B. In BFS of Directed Graph there is no back edge and forward edges. C. In BFS of UDG for each back edge(u,v) we have 0<= v.d <= u.d D. Both b and c. Ans. A
asked
Aug 21, 2018
in
DS
by
Na462
Loyal
(
6.9k
points)

600
views
bfs
datastructure
graphalgorithms
0
votes
0
answers
15
Twin Pointer
Anyone, please explain briefly! Applying BFS on the undirected graph gives you twin pointer.
asked
Aug 21, 2018
in
Algorithms
by
syncronizing
Junior
(
815
points)

47
views
bfs
twinpointer
+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.7k
points)

99
views
dfs
bfs
0
votes
0
answers
17
Data structures
Is there any graph whose number of BFS and DFS traversals are different?If so which graph.
asked
Aug 5, 2018
in
Programming
by
AIkiran01
(
119
points)

46
views
bfs
datastructure
0
votes
0
answers
18
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.6k
points)

90
views
dfs
bfs
algorithms
0
votes
2
answers
19
BFS Traversal
How through a BFS we can find graph is connected or disconnected? Plz give some example and explain
asked
Jun 30, 2018
in
Algorithms
by
srestha
Veteran
(
117k
points)

86
views
bfs
algorithms
graphalgorithms
0
votes
0
answers
20
BFSBreadth first search
State True or False with explanation The depth of a breadthfirst search tree on an undirected graph $G = (V, E)$ from an arbitrary vertex $v \in V$ is the diameter of the graph $G$. (The diameter $d$ of a graph is the smallest $d$ such that every pair of vertices $s$ and $t$ have $\delta(s, t) \leq d$)
asked
Mar 21, 2018
in
DS
by
akshat sharma
Active
(
2.1k
points)

196
views
bfs
datastructure
+6
votes
1
answer
21
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.3k
points)

1.8k
views
algorithms
bfs
dfs
graphalgorithms
programminginc
datastructure
+1
vote
1
answer
22
BFS No of Teversals
How to solve these kind of questions?
asked
Jan 17, 2018
in
DS
by
Shubham Kumar Gupta
(
449
points)

149
views
bfs
algorithms
datastructure
graphalgorithms
+1
vote
0
answers
23
Test Series
consider a graph. Let S is starting point to traverse. At any time instance, what will be the maximum length of the queue if we apply BFS for the aboveundirected graph?( Marks: 0.66 ) 5 2 4 3 I think answer should be Option(3) i.e. 4 elements ... Further steps will reduce the length of the queue. So maximum length of the queue at any instance is 4. Please correct me if I am wrong.
asked
Jan 13, 2018
in
Algorithms
by
ankit_thawal
Active
(
1.4k
points)

66
views
bfs
+2
votes
0
answers
24
NO Of BFS traversal
what is the question asking exactly?
asked
Jan 11, 2018
in
Programming
by
gari
Active
(
3.5k
points)

148
views
bfs
algorithms
graphalgorithms
datastructure
0
votes
0
answers
25
BFS traversal sequence
Starting vertex is : $V_1$ Find the BFS traversal sequence
asked
Dec 12, 2017
in
Algorithms
by
Tuhin Dutta
Loyal
(
9.7k
points)

109
views
algorithms
bfs
graphalgorithms
datastructure
0
votes
1
answer
26
#Graphs #DS BFS AND DFS Question?
Can BFS and DFS both work cyclic and acyclic graphs?! Kindly explain for each of 'em. Thank you!
asked
Dec 9, 2017
in
Algorithms
by
iarnav
Loyal
(
8.3k
points)

381
views
algorithms
bfs
dfs
graphalgorithms
datastructure
0
votes
0
answers
27
BFS algorithm
$State \ TRUE \ OR \ FALSE :\\ Given \ an \ undirected \ connected \ graph \ with \ binary \ edge \ weights \ the \\ shortest \ path \ b/w \ any \ two \ nodes \ can \ be \ found \ in \ O(E)?$
asked
Dec 8, 2017
in
Algorithms
by
saxena0612
Boss
(
11.8k
points)

61
views
bfs
algorithms
0
votes
1
answer
28
Breadth first Search
asked
Nov 26, 2017
in
Algorithms
by
VS
Boss
(
10.5k
points)

150
views
bfs
graphalgorithms
0
votes
1
answer
29
TestSeries
Can Bfs be applied for topological sort?
asked
Nov 16, 2017
in
Algorithms
by
shreyansh jain
Active
(
2.2k
points)

67
views
bfs
0
votes
0
answers
30
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
asked
Nov 7, 2017
in
Computer Networks
by
Manoja Rajalakshmi A
Boss
(
11.4k
points)

178
views
computernetworks
dfs
bfs
Page:
1
2
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged bfs
Recent Blog Comments
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
bro can be upload all standard book questions in...
it'll take 34 days but for most purpose you can...
50,648
questions
56,422
answers
195,193
comments
99,823
users