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 917 views
29 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 13.9k views
10 votes
2 answers
Answer the following: 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 ... 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.1k 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.2k 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.5k 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 873 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.6k views
To see more, click for the full list of questions or popular tags.