Which one of the following statements is false?
| A. |
Optimal binary search tree construction can be performed efficiently using dynamic programmmg.
|
| B. |
Breadth-first search cannot be used to find connected components of a graph.
|
| C. |
Given the prefix and postfix walks of a binary tree, the binary tree cannot be uniquely reconstructed.
|
| D. | Both (b) and (c) |
Answer : D Explanation :
Here option (B) is also false because 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. so ans is both 'A' and 'C'
 |
|
|
Option: A Explanation : Explanation will come here. Explanation will come here. Explanation will come here. Explanation will come here. Explanation will come here. |
