Consider the task of finding the shortest path in an unweighted graph by using BFS and DFS. Which of the following statements are true? $$ \text{ (A) BFS always finds the shortest path } $$ $$ \text{ (B). DFS always finds the shortest path.} $$ $$ \text{ (C). DFS does not guarantee finding the shortest path } $$ $$ \text{ (D). BFS does not guarantee finding the shortest path } $$
Step-by-step Solution:
In an unweighted graph, the cost of every edge is the same (i.e., each edge has weight 1).
- BFS (Breadth First Search):
BFS explores all neighbors level by level.
Therefore, the first time it reaches a vertex, it must be through the shortest path (minimum number of edges).
⇒ BFS always finds the shortest path.
- DFS (Depth First Search):
DFS goes deep into one path before exploring alternatives.
This may result in reaching a node via a longer path first, even though a shorter path exists.
⇒ DFS does not guarantee the shortest path.
✅ Correct Answer: (A) and (C) only