search
Log In

Recent questions tagged bfs

0 votes
1 answer
1
What are the appropriate data structures for graph traversal using Breadth First Search(BFS) and Depth First Search(DFS) algorithms? Stack for BFS and Queue for DFS Queue for BFS and Stack for DFS Stack for BFS and Stack for DFS Queue for BFS and Queue for DFS
asked Mar 30 in Graph Theory Lakshman Patel RJIT 74 views
1 vote
3 answers
2
$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 Satbir 617 views
0 votes
1 answer
3
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 shortest-path 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 KUSHAGRA गुप्ता 159 views
1 vote
1 answer
4
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 have a list of r pairs of ... that each rivalry is 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 KUSHAGRA गुप्ता 192 views
1 vote
1 answer
5
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$ , the unique simple path in the graph $(V, E_{\Pi})$ from s to v is a shortest path in G, yet the 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 KUSHAGRA गुप्ता 167 views
1 vote
2 answers
6
What will be the path from A-H if BFS is used in the following graph?
asked Feb 2, 2019 in Algorithms saptarshiDey 166 views
0 votes
0 answers
7
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 Markzuck 411 views
0 votes
1 answer
8
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 implies ... construct 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 Sandy Sharma 322 views
1 vote
0 answers
9
Does Back Edges in both BFS and DFS leads to cycle in a directed graph? Please elaborate.
asked Nov 26, 2018 in Algorithms Shamim Ahmed 116 views
0 votes
0 answers
10
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 algorithm I have used is the ... by "redtuna" in the selected answer here. https://stackoverflow.com/questions/29631211/edge-classification-during-breadth-first-search-on-a-directed-graph
asked Nov 22, 2018 in Programming Ayush Upadhyaya 834 views
0 votes
0 answers
11
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 codingo1234 78 views
0 votes
0 answers
12
$0-1$ $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 $0-1$ $BFS?$ $A)$ Priority queue $B)$Stack $C)$ Double-ended queue $D)$ Linked list
asked Nov 13, 2018 in Algorithms Lakshman Patel RJIT 119 views
0 votes
1 answer
13
Maximum number of BFS Traversal Possible on BST of height 3 is ..........
asked Oct 21, 2018 in Programming Na462 170 views
2 votes
1 answer
14
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 sushmita 158 views
0 votes
0 answers
15
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 syncronizing 553 views
4 votes
0 answers
16
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 Na462 1.2k views
0 votes
0 answers
17
Anyone, please explain briefly! Applying BFS on the undirected graph gives you twin pointer.
asked Aug 21, 2018 in Algorithms syncronizing 136 views
1 vote
2 answers
18
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 determine the ... the 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 Prince Sindhiya 189 views
0 votes
0 answers
19
Is there any graph whose number of BFS and DFS traversals are different?If so which graph.
asked Aug 5, 2018 in Programming AIkiran01 68 views
0 votes
0 answers
20
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 Rishav Kumar Singh 195 views
0 votes
2 answers
21
How through a BFS we can find graph is connected or disconnected? Plz give some example and explain
asked Jun 30, 2018 in Algorithms srestha 137 views
2 votes
3 answers
22
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 Arjun 949 views
0 votes
0 answers
23
State True or False with explanation The depth of a breadth-first 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 akshat sharma 331 views
6 votes
1 answer
24
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 graph G, the edges of G will ... as tree edge, 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 MIRIYALA JEEVAN KUMA 3.6k views
1 vote
1 answer
25
1 vote
0 answers
26
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 above-undirected graph?( Marks: -0.66 ) 5 2 4 3 I think answer should be Option(3) i.e. 4 elements Procedure: 1 ... y 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 ankit_thawal 82 views
2 votes
0 answers
27
what is the question asking exactly?
asked Jan 11, 2018 in Programming gari 208 views
0 votes
0 answers
28
Starting vertex is : $V_1$ Find the BFS traversal sequence
asked Dec 12, 2017 in Algorithms Tuhin Dutta 141 views
0 votes
1 answer
29
Can BFS and DFS both work cyclic and acyclic graphs?! Kindly explain for each of 'em. Thank you!
asked Dec 9, 2017 in Algorithms iarnav 431 views
...