Dark Mode

Recent questions tagged breadth-first-search

0 votes

0 answers

1

Memory Based GATE DA 2024 | Question: 34
BFS DFS question asking the number of nodes expanded BFS = DFS BFS $ DFS None

GO Classes asked in Algorithms Feb 4

115 views

3 votes

2 answers

2

GATE Data Science and Artificial Intelligence 2024 | Sample Paper | Question: 52
Consider the following undirected graph on $5$ nodes. Assume you are performing breadth-first search on this graph using a queue data structure. How many unique breadth first orderings are possible on this graph? $9$ $24$ $48$ $120$

admin asked in Others Oct 21, 2023

by admin

2.1k views

10 votes

1 answer

3

GATE CSE 2023 | Question: 46
Let $U=\{1,2,3\}$. Let $2^{U}$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^{U}$. For any $A, B \in 2^{U},(A, B)$ is an edge in $G$ if and only if (i) $A \neq B$, and (ii) ... $A$ is denoted by $\mathcal{B}(A)$. If $\emptyset$ denotes the empty set, then the cardinality of $\mathcal{B}(\emptyset)$ is ______________.

admin asked in Algorithms Feb 15, 2023

by admin

6.3k views

1 vote

0 answers

4

DRDO CSE 2022 Paper 1 | Question: 33 (a)
Consider the following graph. How many nodes (apart from $s$) does the Breadth First Search algorithm discover before discovering $t$ when starting from $s$.

admin asked in Algorithms Dec 15, 2022

by admin

332 views

0 votes

1 answer

5

#Dfs And Bfs
Please list the problems where BFS alone can do and DFS alone can do and both can do??

Subbu. asked in Algorithms Jul 16, 2022

by Subbu.

329 views

0 votes

0 answers

6

Self Doubt - BFT Applications
Can we use BFT for finding no. of connected components in a directed as well as undirected graph?

Vallari Garg asked in DS May 16, 2022

by Vallari Garg

342 views

0 votes

1 answer

7

UGC NET CSE | October 2020 | Part 2 | Question: 63
Which of the following statements are true? Minimax search is breadth-first; it processes all the nodes at a level before moving to a node in next level. The effectiveness of the alpha-beta pruning is highly dependent on the order in which the states are examined The ... only $(i)$ and $(iv)$ only $(ii)$ and $(iii)$ only $(iii)$ and $(iv)$ only

go_editor asked in DS Nov 20, 2020

2.2k views

1 vote

2 answers

8

NIELIT 2017 July Scientist B (IT) - Section B: 4
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

admin asked in DS Mar 30, 2020

by admin

1.4k views

2 votes

3 answers

9

ISRO2020-32
$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$

Satbir asked in DS Jan 13, 2020

by Satbir

4.0k views

0 votes

1 answer

10

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 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.

KUSHAGRA गुप्ता asked in Algorithms Nov 12, 2019

by KUSHAGRA गुप्ता

921 views

1 vote

1 answer

11

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.

KUSHAGRA गुप्ता asked in Algorithms Nov 12, 2019

by KUSHAGRA गुप्ता

1.1k views

1 vote

1 answer

12

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.

KUSHAGRA गुप्ता asked in Algorithms Nov 12, 2019

by KUSHAGRA गुप्ता

1.5k views

1 vote

2 answers

13

BFS traversal path
What will be the path from A-H if BFS is used in the following graph?

saptarshiDey asked in Algorithms Feb 1, 2019

by saptarshiDey

823 views

1 vote

0 answers

14

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.

Markzuck asked in Algorithms Dec 30, 2018

1.4k views

0 votes

1 answer

15

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 ?

Sandy Sharma asked in Algorithms Dec 25, 2018

by Sandy Sharma

1.4k views

0 votes

1 answer

16

ME OTS
Are the "n!" ways maximum possible BFS sequences ? ( Indirectly, for any given vertices is it obvious that complete graph will give max BFS sequences ? )

HeadShot asked in Algorithms Nov 30, 2018

262 views

1 vote

0 answers

17

Algorithm Back Edges
Does Back Edges in both BFS and DFS leads to cycle in a directed graph? Please elaborate.

Shamim Ahmed asked in Algorithms Nov 26, 2018

by Shamim Ahmed

453 views

0 votes

0 answers

18

Edge-Classification 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 selected answer here. https://stackoverflow.com/questions/29631211/edge-classification-during-breadth-first-search-on-a-directed-graph

Ayush Upadhyaya asked in Programming in C Nov 22, 2018

by Ayush Upadhyaya

3.3k views

0 votes

1 answer

19

BFS TRAVERSAL
HOW CAN WE GET A CROSS EDGE WHILE PERFORMING A BFS ON UNDIRECTED AND DIRECTED GRAPH CAN ANYONE SHOW WITH AN EXAMPLE?

codingo1234 asked in Programming in C Nov 21, 2018

375 views

0 votes

0 answers

20

Breadth First Search(BFS)
$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

Lakshman Bhaiya asked in Algorithms Nov 13, 2018

by Lakshman Bhaiya

446 views

0 votes

0 answers

21

BFS TREE EDGES
WHAT ARE THE VARIOUS EDGES POSSIBLE DURING BFS ?

eyeamgj asked in Algorithms Oct 29, 2018

257 views

0 votes

1 answer

22

BFS Traversal
Maximum number of BFS Traversal Possible on BST of height 3 is ..........

Na462 asked in Programming in C Oct 21, 2018

by Na462

1.0k views

2 votes

1 answer

23

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?

sushmita asked in DS Oct 3, 2018

594 views

0 votes

1 answer

24

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.

syncronizing asked in DS Aug 23, 2018

by syncronizing

2.5k views

4 votes

0 answers

25

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

Na462 asked in DS Aug 21, 2018

by Na462

3.9k views

0 votes

0 answers

26

Twin Pointer
Anyone, please explain briefly! Applying BFS on the undirected graph gives you twin pointer.

syncronizing asked in Algorithms Aug 21, 2018

by syncronizing

498 views

Page:

1
2
3
next »

Recent questions tagged breadth-first-search