10 PYQ / MCQ questions related to.BFS (Breadth-First Search) and DFS (Depth-First Search)

Here are some MCQ questions related to BFS (Breadth-First Search) and DFS (Depth-First Search) with descriptions:

1. GATE CS 2020
Which data structure is commonly used to implement Breadth-First Search (BFS)?
A) Stack
B) Queue
C) Priority Queue
D) Linked List
Answer: B) Queue
Description: BFS explores nodes level by level and uses a queue to store the nodes to be visited next.

2. UGC NET 2019
Which data structure is commonly used to implement Depth-First Search (DFS)?
A) Queue
B) Stack
C) Priority Queue
D) Binary Tree
Answer: B) Stack
Description: DFS uses a stack to explore the deepest nodes first before backtracking. A recursive implementation uses the call stack.

3. ISRO Scientist 2018
The time complexity of Breadth-First Search (BFS) for a graph with $V$ vertices and $E$ edges is:
A) O(V + E)
B) O(V²)
C) O(E²)
D) O(V * E)
Answer: A) O(V + E)
Description: BFS traverses every vertex and edge at most once, resulting in a linear time complexity.

4. GATE CS 2017
In which scenario is DFS preferred over BFS?
A) Finding the shortest path
B) Detecting cycles in a graph
C) Level-order traversal
D) Topological sorting
Answer: B) Detecting cycles in a graph
Description: DFS is efficient for cycle detection and topological sorting, while BFS is better for finding shortest paths in unweighted graphs.

5. NIELIT Scientist B 2019
Which traversal technique is used in finding connected components of an undirected graph?
A) BFS
B) DFS
C) Both A and B
D) None of these
Answer: C) Both A and B
Description: Both BFS and DFS can be used to find connected components by visiting all reachable nodes from each unvisited vertex.

6. GATE CS 2018
Which of the following is true regarding DFS and BFS in a tree?
A) Both traverse all nodes
B) BFS requires more space than DFS
C) DFS requires more space than BFS
D) Both have the same space complexity
Answer: B) BFS requires more space than DFS
Description: BFS stores all child nodes at each level, while DFS only needs to store nodes along the current path, so BFS typically uses more space.

7. UGC NET 2020
Which of the following traversal techniques uses backtracking?
A) BFS
B) DFS
C) Dijkstra’s Algorithm
D) Prim’s Algorithm
Answer: B) DFS
Description: DFS uses backtracking to explore all possible paths before moving to the next branch.

8. GATE CS 2016
Which of the following is NOT a characteristic of BFS?
A) Uses a queue
B) Suitable for finding shortest paths in unweighted graphs
C) Can detect cycles in a graph
D) Uses recursion
Answer: D) Uses recursion
Description: BFS typically uses an iterative approach with a queue, while DFS may use recursion.

9. NIELIT Scientist B 2021
If a graph has V vertices and E edges, what is the space complexity of DFS using an adjacency list?
A) O(V)
B) O(E)
C) O(V + E)
D) O(V²)
Answer: C) O(V + E)
Description: Storing the graph in an adjacency list takes O(V + E) space, and the DFS traversal itself uses O(V) space for the recursion stack.

10. GATE CS 2015
What is the primary difference between BFS and DFS?
A) BFS uses backtracking, DFS does not
B) DFS uses a queue, BFS uses a stack
C) BFS explores level by level, DFS goes deep
D) Both use the same traversal strategy
Answer: C) BFS explores level by level, DFS goes deep
Description: BFS explores each level fully before moving deeper, while DFS goes as deep as possible along one branch before backtracking.