Log In

Recent questions tagged graph-search

1 vote
2 answers
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 (Depth First Search) tree rooted at a vertex is atleast as depth of any BFS tree rooted at the same vertex. Both (a) and (c)
asked Jan 4, 2019 in Algorithms Abhishek Kumar 38 957 views
30 votes
9 answers
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$ is between two nodes ... $\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
asked Feb 14, 2018 in Algorithms gatecse 15.1k views
24 votes
6 answers
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}$
asked Feb 14, 2017 in Algorithms Madhav 3.9k views
10 votes
2 answers
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. Depth first search ... components of a graph. Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.
asked Nov 27, 2016 in DS makhdoom ghaya 2.3k views
5 votes
1 answer
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?
asked Oct 26, 2016 in Algorithms Geet 1.3k views
3 votes
1 answer
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
asked Aug 1, 2016 in Algorithms jothee 2.7k views
1 vote
1 answer
$\alpha - \beta$ cutoffs are applied to Depth first search Best first search Minimax search Breadth first search
asked Jul 22, 2016 in Algorithms jothee 928 views
2 votes
1 answer
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
asked Jul 7, 2016 in Algorithms jothee 1.7k views
39 votes
7 answers
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^{th}$ vertex in this BFS traversal, then the maximum possible value of $n$ is __________
asked Feb 12, 2016 in Algorithms Akash Kanase 6.2k views
34 votes
9 answers
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$ ... of $G$ that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$? $-1$ $0$ $1$ $2$
asked Feb 13, 2015 in Algorithms makhdoom ghaya 10k views
47 votes
10 answers
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$
asked Nov 3, 2014 in Algorithms Ishrat Jahan 9.8k views
22 votes
6 answers
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 vertex $u$ ... connected There are two connected components, and $Q$ and $R$ are connected There are two connected components, and $P$ and $Q$ are connected
asked Nov 1, 2014 in Algorithms Ishrat Jahan 5.4k views
34 votes
10 answers
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]$
asked Oct 30, 2014 in Algorithms Ishrat Jahan 7k views
19 votes
4 answers
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 node $a$. The nodes ... they are 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
asked Oct 29, 2014 in Algorithms Ishrat Jahan 3.6k views
36 votes
4 answers
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 _________.
asked Sep 28, 2014 in Algorithms jothee 6.3k views
37 votes
5 answers
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 from $W$ to every vertex in the graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.
asked Sep 28, 2014 in Algorithms jothee 6.3k views
25 votes
4 answers
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)$
asked Sep 26, 2014 in Algorithms jothee 6.7k views
20 votes
4 answers
Consider the following graph: Among the following sequences: abeghf abfehg abfhge afghbe Which are the depth-first traversals of the above graph? I, II and IV only I and IV only II, III and IV only I, III and IV only
asked Sep 16, 2014 in Algorithms Kathleen 5.4k views
29 votes
7 answers
Consider an undirected, unweighted graph $G$. Let a breadth-first traversal of $G$ be done starting from a node $r$. Let $d(r,u)$ and $d(r,v)$ be the lengths of the shortest paths from $r$ to $u$ and $v$ respectively in $G$. If $u$ is visited before $v$ during the breadth-first traversal, which ... statements is correct? $d(r,u) < d(r,v)$ $d(r,u) > d(r,v)$ $d(r,u) \leq d(r,v)$ None of the above
asked Sep 15, 2014 in Algorithms Kathleen 7.4k views
21 votes
3 answers
The most appropriate matching for the following pairs $\begin{array}{|l|l|}\hline \text{X: depth first search} & \text{1: heap } \\\hline \text{Y: breadth first search} & \text{2: queue} \\\hline \text{Z: sorting} & \text{3: stack} \\\hline \end{array}$ is: $\text{X - 1, Y - 2, Z - 3}$ $\text{X - 3, Y - 1, Z - 2}$ $\text{X - 3, Y - 2, Z - 1}$ $\text{X - 2, Y - 3, Z - 1}$
asked Sep 14, 2014 in Algorithms Kathleen 2.9k views
22 votes
5 answers
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is: $\text{MNOPQR}$ $\text{NQMPOR}$ $\text{QMNPRO}$ $\text{QMNPOR}$
asked Sep 12, 2014 in Algorithms Kathleen 13.7k views
To see more, click for the full list of questions or popular tags.