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. BFS explores level by level, ensuring the shortest path in unweighted graphs.
- (B) DFS always finds the shortest path: False. DFS prioritizes depth over breadth, not guaranteeing the shortest path due to its backtracking nature.
- (C) DFS does not guarantee finding the shortest path: True. As explained, DFS may not discover the shortest path first.
- (D) BFS does not guarantee finding the shortest path: False. BFS consistently guarantees the shortest path in unweighted graphs.

Step 2: Conclusion.
Statements (B) and (D) are correct, leading to option (1) as the correct answer.