# Recent questions tagged bfs

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
1 vote
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$
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.
1 vote
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.
1 vote
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.
1 vote
6
What will be the path from A-H if BFS is used in the following graph?
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.
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 ?
1 vote
9
Does Back Edges in both BFS and DFS leads to cycle in a directed graph? Please elaborate.
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
11
HOW CAN WE GET A CROSS EDGE WHILE PERFORMING A BFS ON UNDIRECTED AND DIRECTED GRAPH CAN ANYONE SHOW WITH AN EXAMPLE?
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
13
Maximum number of BFS Traversal Possible on BST of height 3 is ..........
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?
15
Which does this sentence mean? In BFS of an undirected graph, there are no back edge and no forward edge.
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
17
Anyone, please explain briefly! Applying BFS on the undirected graph gives you twin pointer.
1 vote
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
19
Is there any graph whose number of BFS and DFS traversals are different?If so which graph.
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.
21
How through a BFS we can find graph is connected or disconnected? Plz give some example and explain
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
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$)
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
1 vote
25
How to solve these kind of questions?
1 vote
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.
Starting vertex is : $V_1$ Find the BFS traversal sequence