Recent questions tagged breadth-first-search / GATE Overflow for GATE CSE

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

BFS DFS question asking the number of nodes expanded BFS = DFSBFS $$ DFSNone

GO Classes

137 views

GO Classes asked Feb 4

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$

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

admin

2.2k views

admin asked Oct 21, 2023

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

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

admin

6.4k views

admin asked Feb 15, 2023

1 votes

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

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

336 views

admin asked Dec 15, 2022

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

Please list the problems where BFS alone can do and DFS alone can do and both can do??

Subbu.

341 views

Subbu. asked Jul 16, 2022

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?

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

Vallari Garg

343 views

Vallari Garg asked May 16, 2022

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

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

go_editor

2.3k views

go_editor asked Nov 20, 2020

3 votes

1 answer

8

GATE Overflow Test Series | Algorithms | Test 2 | Question: 27
Let $G = (V, E)$ be a simple undirected graph with all edge weights being unity, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search ( ... that is not in $T$, then the number of possible values of $d(u) - d(v)$ is $\_\_\_\_\_\_\_.$

Let $G = (V, E)$ be a simple undirected graph with all edge weights being unity, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote ...

gatecse

352 views

gatecse asked Sep 7, 2020

1 votes

2 answers

9

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

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

admin

1.4k views

admin asked Mar 30, 2020

2 votes

3 answers

10

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$

$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,\ v6v...

Satbir

4.1k views

Satbir asked Jan 13, 2020

0 votes

1 answer

11

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.

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

KUSHAGRA गुप्ता

964 views

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

1 votes

1 answer

12

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.

There are two types of professional wrestlers: “babyfaces” (“good guys”) and “heels” (“bad guys”). Between any pair of professional wrestlers, there may o...

KUSHAGRA गुप्ता

1.2k views

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

1 votes

1 answer

13

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.

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

KUSHAGRA गुप्ता

1.7k views

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

1 votes

2 answers

14

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

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

saptarshiDey

855 views

saptarshiDey asked Feb 1, 2019

1 votes

0 answers

15

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.

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

Markzuck

1.4k views

Markzuck asked Dec 30, 2018

0 votes

1 answer

16

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 ?

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 FalseExplanation:FALSE....

Sandy Sharma

1.4k views

Sandy Sharma asked Dec 25, 2018

0 votes

1 answer

17

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 ? )

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

277 views

HeadShot asked Nov 30, 2018

1 votes

0 answers

18

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

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

Shamim Ahmed

456 views

Shamim Ahmed asked Nov 26, 2018

0 votes

0 answers

19

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

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

Ayush Upadhyaya

3.3k views

Ayush Upadhyaya asked Nov 22, 2018

0 votes

1 answer

20

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

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

codingo1234

378 views

codingo1234 asked Nov 21, 2018

0 votes

0 answers

21

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

$0-1$ $BFS$ (Breadth First Search)al is used to find the shortest distance between two nodes in a graph providedthat the edges in the graph have the weights $0$ or $1.$Wh...

Lakshman Bhaiya

451 views

Lakshman Bhaiya asked Nov 13, 2018

0 votes

0 answers

22

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

WHAT ARE THE VARIOUS EDGES POSSIBLE DURING BFS ?

eyeamgj

253 views

eyeamgj asked Oct 29, 2018

0 votes

1 answer

23

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

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

Na462

1.0k views

Na462 asked Oct 21, 2018

2 votes

1 answer

24

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?

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

sushmita

597 views

sushmita asked Oct 3, 2018

0 votes

1 answer

25

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.

Which does this sentence mean?In BFS of an undirected graph, there are no back edge and no forward edge.

syncronizing

2.6k views

syncronizing asked Aug 23, 2018

4 votes

0 answers

26

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

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

Na462

3.9k views

Na462 asked Aug 21, 2018

0 votes

0 answers

27

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

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

syncronizing

499 views

syncronizing asked Aug 21, 2018

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