Question

Consider the task of finding the shortest path in an unweighted graph by using BFS and DFS. Which of the following statements are true?
(A). BFS always finds the shortest path.
(B). DFS always finds the shortest path.
(C). DFS does not guarantee finding the shortest path.
(D). BFS does not guarantee finding the shortest path.

• (B) and (D) only
• (A) and (C) only
• (A) and (B) only
• (C) and (D) only

Hint:

BFS guarantees the shortest path in an unweighted graph, while DFS might not, as it explores nodes deeply without regard to path length.

Answer 1

The Correct Option is A

Step 1: Analysis of BFS and DFS.
- **(A)** BFS always finds the shortest path: True, as BFS explores nodes level by level, guaranteeing the shortest path in an unweighted graph.
- **(B)** DFS always finds the shortest path: False, DFS does not guarantee the shortest path because it explores as deep as possible along a branch before backtracking.
- **(C)** DFS does not guarantee finding the shortest path: True, as discussed, DFS does not necessarily explore the shortest path.
- **(D)** BFS does not guarantee finding the shortest path: False, BFS always guarantees the shortest path in an unweighted graph.

Step 2: Conclusion.
The correct statements are **(B) and (D) only**, so the correct answer is **(1)**.