1.9k views

Which of the following statements is false?

1. Optimal binary search tree construction can be performed efficiently using dynamic programming
2. Breadth-first search cannot be used to find connected components of a graph
3. Given the prefix and postfix walks of a binary tree, the tree cannot be re-constructed uniquely
4. Depth-first-search can be used to find the components of a graph
1. 1
2. 2
3. 3
4. 4
asked in Others | 1.9k views
+3

This should be merged with:

https://gateoverflow.in/2465/gate1994-1-22

BFS and DFS both algorithm are used to find connected component. For example: In BFS, a search that begins at some particular vertex 'v' will find the entire connected component containing v (and no more) before returning. To find all the connected components of a graph, loop through its vertices, starting a new breadth first  search whenever the loop reaches a vertex that has not already been included in a previously found connected component. For example:If we do the breadth first traversal of the above graph and print the visited node as the output, it will print the following output. “A B C D E F”. The BFS visits the nodes level by level, so it will start with level 0 which is the root node, and then it moves to the next levels which are B, C and D, then the last levels which are E and F.

In BFS, a search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning. To find all the connected components of a graph, loop through its vertices, starting a new breadth first  search whenever the loop reaches a vertex that has not already been included in a previously found connected component.

(c) True. because: inorder is needed
(d) True. ref: https://www.quora.com/Why-is-DFS-preferred-for-finding-connected-components-in-directed-graphs

answered by Active (3.9k points)
+2
0
But for binary tree in order is always sorted sequence then why we can't create from pre and post order ??
0

@chintain Patel . Only binary search tree inorder is always a sorted sequence.

0

adeebafatima1  thank you actually its kind of tricky way to ask.. tq...next time i willbe careful!!

0
What do we mean by optimal binary search tree??IS it same as AVL  tree??

1
+1 vote
2
–1 vote