GATE CS 1994 Q1.22 — Graph Traversals (BFS, DFS)

To find the false statement, let us analyze each option:

• Option A: Optimal binary search tree (OBST) construction can be performed efficiently using dynamic programming.
  True. The OBST problem has optimal substructure and overlapping subproblems, allowing it to be solved efficiently in $O(n^3)$ time using dynamic programming.
• Option B: Breadth-first search cannot be used to find connected components of a graph.
  False. Both Breadth-First Search (BFS) and Depth-First Search (DFS) can be used to find the connected components of an undirected graph. By starting a BFS from an unvisited vertex, we can traverse and mark all vertices in its connected component, repeating this process for any remaining unvisited vertices.
• Option C: Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.
  True. Preorder (prefix) and postorder (postfix) traversals are not sufficient to uniquely reconstruct a general binary tree. For example, a tree with root $A$ and a single child $B$ will have the prefix walk $A, B$ and postfix walk $B, A$ regardless of whether $B$ is a left child or a right child.
• Option D: Depth-first search can be used to find connected components of a graph.
  True. Just like BFS, DFS can traverse all reachable vertices from a starting node to identify a connected component.

Therefore, statement B is false.