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
+1
vote
2
answers
1
ISRO202032
$G$ is an undirected graph with vertex set $\{v1,v2,v3,v4,v5,v6,v7\}$ and edge set $\{v1v2,\ v1v3,\ v1v4\ ,v2v4,\ v2v5,\ v3v4,\ v4v5,\ v4v6,\ v5v6,\ v6v7\ \}$. A breadth first search of the graph is performed with $v1$ as the root node. Which of the following is a tree edge ? $v2v4$ $v1v4$ $v4v5$ $v3v4$
asked
Jan 13
in
DS
by
Satbir
Boss
(
23.8k
points)

159
views
isro2020
datastructures
bfs
normal
0
votes
1
answer
2
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, 2019
in
Algorithms
by
Kushagra गुप्ता
Active
(
4k
points)

88
views
cormen
graphalgorithms
bfs
descriptive
+1
vote
0
answers
3
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, 2019
in
Algorithms
by
Kushagra गुप्ता
Active
(
4k
points)

41
views
cormen
graphalgorithms
bfs
descriptive
0
votes
0
answers
4
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, 2019
in
Algorithms
by
Kushagra गुप्ता
Active
(
4k
points)

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

98
views
graphalgorithms
algorithms
bfs
datastructures
0
votes
0
answers
6
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)

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

174
views
algorithms
graphalgorithms
dfs
datastructures
bfs
+1
vote
0
answers
8
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)

89
views
algorithms
bfs
dfs
0
votes
0
answers
9
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
(
29k
points)

368
views
graphalgorithms
bfs
0
votes
0
answers
10
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
(
933
points)

53
views
bfs
algorithms
graphalgorithms
0
votes
0
answers
11
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
(
58.8k
points)

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

96
views
bfs
algorithms
datastructures
+2
votes
1
answer
13
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.6k
points)

101
views
bfs
datastructures
graphalgorithms
0
votes
0
answers
14
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
(
835
points)

326
views
programminginc
datastructures
bfs
+4
votes
0
answers
15
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
(
7k
points)

698
views
bfs
datastructures
graphalgorithms
0
votes
0
answers
16
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
(
835
points)

50
views
bfs
twinpointer
+1
vote
2
answers
17
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)

106
views
dfs
bfs
0
votes
0
answers
18
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)

49
views
bfs
datastructures
0
votes
0
answers
19
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)

104
views
dfs
bfs
algorithms
0
votes
2
answers
20
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
(
119k
points)

90
views
bfs
algorithms
graphalgorithms
+2
votes
3
answers
21
ISRO201833
Which of the following is application of Breath First Search on the graph? Finding diameter of the graph Finding bipartite graph Both (a) and (b) None of the above
asked
Apr 22, 2018
in
Algorithms
by
Arjun
Veteran
(
431k
points)

688
views
isro2018
graphalgorithms
bfs
algorithms
0
votes
0
answers
22
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)

208
views
bfs
datastructures
+6
votes
1
answer
23
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.2k
views
algorithms
bfs
dfs
graphalgorithms
programminginc
datastructures
+1
vote
1
answer
24
BFS No of Teversals
How to solve these kind of questions?
asked
Jan 17, 2018
in
DS
by
Shubham Kumar Gupta
(
449
points)

164
views
bfs
algorithms
datastructures
graphalgorithms
+1
vote
0
answers
25
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)

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

161
views
bfs
algorithms
graphalgorithms
datastructures
0
votes
0
answers
27
BFS traversal sequence
Starting vertex is : $V_1$ Find the BFS traversal sequence
asked
Dec 12, 2017
in
Algorithms
by
Tuhin Dutta
Boss
(
10.6k
points)

112
views
algorithms
bfs
graphalgorithms
datastructures
0
votes
1
answer
28
#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.4k
points)

388
views
algorithms
bfs
dfs
graphalgorithms
datastructures
0
votes
0
answers
29
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.9k
points)

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

158
views
bfs
graphalgorithms
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged bfs
Recent Blog Comments
100 percent
I am getting 151 marks excluding question not...
everyone will be surprised seeing the cutoff this...
There is no point of any debate/discourse here....
absolutely right
50,737
questions
57,286
answers
198,191
comments
104,872
users