Dark Mode

Recent questions tagged graph-search

0 votes

1 answer

1

NPTEL Assignment Question
Consider the following strategy to solve the single source shortest path problem with edge weights from source s. 1. Replace each edge with weight w by w edges of weight 1 connected by new intermediate nodes 2. Run BFS(s) on the modified graph to ... 's algorithm.s st This strategy will not solve the problem correctly. This strategy will only work if the graph is acyclic.

rsansiya111 asked in Algorithms Dec 8, 2021

436 views

1 vote

2 answers

2

MadeEasy Test Series: Algorithms - Graph Algorithms
Which of the following statement is true? For a directed graph, the absence of back edges in a DFS tree can have cycle. If all edge in a graph have distinct weight then the shortest path between two vertices is unique. The depth of any DFS ( ... tree rooted at a vertex is atleast as depth of any BFS tree rooted at the same vertex. Both (a) and (c)

Abhishek Kumar 38 asked in Algorithms Jan 4, 2019

by Abhishek Kumar 38

2.1k views

1 vote

4 answers

3

algorithm
In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as x/yx/y, where x is discovery time stamp and y is finishing time stamp It shows which of the following depth first forest? {a,b,e} {c,d,f,g,h} {a,b,e} {c,d,h} {f,g} {a,b,e} {f,g} {c,d} {h} {a,b,c,d} {e,f,g} {h}

eyeamgj asked in Algorithms May 10, 2018

1.6k views

0 votes

1 answer

4

Self Doubt
How can we distinguish b/w back edge, the forward edge and cross edge in BFS or DFS traversal in Graphs?

Durgesh Singh asked in Algorithms Apr 29, 2018

by Durgesh Singh

182 views

43 votes

7 answers

5

GATE CSE 2018 | Question: 30
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ ... $\mid i-j \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II

gatecse asked in Algorithms Feb 14, 2018

22.8k views

0 votes

1 answer

6

Test Series
Please explain why first option is wrong

Diksha Aswal asked in Algorithms Dec 4, 2017

by Diksha Aswal

477 views

1 vote

1 answer

7

Kuldeep Pal asked in Algorithms Jul 16, 2017

159 views

2 votes

1 answer

8

#GRAPH_ALGORITHM
I want to know in which condition we should apply BFS and DFS for GRAPH Search ? And why?

Akashsaha asked in Algorithms May 5, 2017

258 views

27 votes

5 answers

9

GATE CSE 2017 Set 2 | Question: 15
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below? $\text{MNOPQR}$ $\text{NQMPOR}$ $\text{QMNROP}$ $\text{POQNMR}$

Madhav asked in Algorithms Feb 14, 2017

by Madhav

6.3k views

5 votes

1 answer

10

Testbook live Testseries
Which of the following statements are false ? $1.$ A depth-first search of a directed graph always produces the same number of tree edges (i.e., independent of the order in which the vertices are provided and independent of the order of the ... between any two vertices will not change. $4.$ Dijkstra's algorithm may not terminate if the graph contains negative weight edges.

Akriti sood asked in Algorithms Jan 23, 2017

1.4k views

13 votes

2 answers

11

GATE CSE 1989 | Question: 3-ixa
Which one of the following statements (s) is/are FALSE? Overlaying is used to run a program, which is longer than the address space of the computer. Optimal binary search tree construction can be performed efficiently by using dynamic programming. ... of a graph. Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.

makhdoom ghaya asked in DS Nov 27, 2016

by makhdoom ghaya

3.1k views

6 votes

1 answer

12

#Algorithm # DFS
Let G be a graph with n vertices and m edges. a. True or false: All its DFS forests (for traversals starting at different vertices) will have the same number of trees? b. True or false: All its DFS forests will have the same number of tree edges and the same number of back edges?

Geet asked in Algorithms Oct 26, 2016

by Geet

2.2k views

3 votes

1 answer

13

UGC NET CSE | Junet 2015 | Part 3 | Question: 58
Which of the following statements is true for Branch-and-Bound search? Underestimates of remaining distance may cause deviation from optimal path Overestimates can't cause right path to be overlooked Dynamic programming principle can be used to discard redundant partial paths All of the above

go_editor asked in Algorithms Aug 1, 2016

3.5k views

1 vote

1 answer

14

UGC NET CSE | September 2013 | Part 3 | Question: 2
$\alpha - \beta$ cutoffs are applied to Depth first search Best first search Minimax search Breadth first search

go_editor asked in Algorithms Jul 22, 2016

1.5k views

2 votes

1 answer

15

UGC NET CSE | June 2012 | Part 3 | Question: 51
The strategy used to reduce the number of tree branches and the number of static evaluations applied in case of a game tree is Minmax strategy Alpha-beta pruning strategy Constraint satisfaction strategy Static max strategy

go_editor asked in Algorithms Jul 7, 2016

2.4k views

45 votes

8 answers

16

GATE CSE 2016 Set 2 | Question: 11
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{\text{th}}$ vertex in this BFS traversal, then the maximum possible value of $n$ is __________

Akash Kanase asked in Algorithms Feb 12, 2016

by Akash Kanase

10.1k views

0 votes

1 answer

17

BFS and DFS predecessor subgraph
The predessor subgraph of BFS is a tree but the predecessor subgraph of DFS is a forest ?? please explain why??

Saurav asked in Algorithms Aug 27, 2015

by Saurav

1.1k views

41 votes

9 answers

18

GATE CSE 2015 Set 1 | Question: 45
Let $G = (V, E)$ be a simple undirected graph, 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 (BFS) is performed starting at $s$. Let $T$ be the ... that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$? $-1$ $0$ $1$ $2$

makhdoom ghaya asked in Algorithms Feb 13, 2015

by makhdoom ghaya

14.3k views

61 votes

10 answers

19

GATE IT 2005 | Question: 14
In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is $k$ $k+1$ $n-k-1$ $n-k$

Ishrat Jahan asked in Algorithms Nov 3, 2014

by Ishrat Jahan

13.8k views

28 votes

8 answers

20

GATE IT 2006 | Question: 47
Consider the depth-first-search of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is first visited, and finish time $f(u)$ represent the time instant when the ... are two connected components, and $Q$ and $R$ are connected There are two connected components, and $P$ and $Q$ are connected

Ishrat Jahan asked in Algorithms Nov 1, 2014

by Ishrat Jahan

8.4k views

45 votes

11 answers

21

GATE IT 2007 | Question: 24
A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which the DFS call to the vertex $u$ terminates. Which of the following statements is always TRUE for all edges $(u, v)$ in the graph ? $d[u] < d[v]$ $d[u] < f[v]$ $f[u] < f[v]$ $f[u] > f[v]$

Ishrat Jahan asked in Algorithms Oct 30, 2014

by Ishrat Jahan

10.6k views

22 votes

3 answers

22

GATE IT 2008 | Question: 47
Consider the following sequence of nodes for the undirected graph given below: $a$ $b$ $e$ $f$ $d$ $g$ $c$ $a$ $b$ $e$ $f$ $c$ $g$ $d$ $a$ $d$ $g$ $e$ $b$ $c$ $f$ $a$ $d$ $b$ $c$ $g$ $e$ $f$ A Depth First Search (DFS) is started at ... first visited. Which of the above is/are possible output(s)? $1$ and $3$ only $2$ and $3$ only $2, 3$ and $4$ only $1, 2$ and $3$ only

Ishrat Jahan asked in Algorithms Oct 29, 2014

by Ishrat Jahan

5.6k views

40 votes

4 answers

23

GATE CSE 2014 Set 3 | Question: 13
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

go_editor asked in Algorithms Sep 28, 2014

9.3k views

44 votes

6 answers

24

GATE CSE 2014 Set 2 | Question: 14
Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing the shortest path between every pair of vertices. the shortest path ... graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.

go_editor asked in Algorithms Sep 28, 2014

8.9k views

29 votes

4 answers

25

GATE CSE 2014 Set 1 | Question: 11
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjacency matrix? $\Theta(n)$ $\Theta(n+m)$ $\Theta(n^2)$ $\Theta(m^2)$

go_editor asked in Algorithms Sep 26, 2014

10.2k views

Page:

Recent questions tagged graph-search