1. What does DFS stand for in graph theory?
(A) Depth First Search
(B) Depth Factor Search
(C) Depth Function Search
(D) Depth Following Search
2. Which data structure is primarily used in DFS?
(A) Queue
(B) Stack
(C) Array
(D) Linked list
3. What does BFS stand for in graph theory?
(A) Best First Search
(B) Breadth First Search
(C) Balanced First Search
(D) Broad First Search
4. Which data structure is primarily used in BFS?
(A) Stack
(B) Queue
(C) Array
(D) Linked list
5. What is the primary use of DFS?
(A) Finding the shortest path
(B) Traversing all vertices of a graph
(C) Finding connected components
(D) Searching for a specific vertex
6. In which traversal method is the root node processed before its children?
(A) BFS
(B) DFS
(C) Both BFS and DFS
(D) Neither BFS nor DFS
7. Which traversal method guarantees the shortest path in an unweighted graph?
(A) DFS
(B) BFS
(C) Both DFS and BFS
(D) Neither DFS nor BFS
8. What is a key characteristic of BFS?
(A) It explores all neighbors before going deeper
(B) It uses a stack for exploration
(C) It can get stuck in cycles
(D) It always finds the longest path
9. In which traversal method is backtracking often used?
(A) BFS
(B) DFS
(C) Both BFS and DFS
(D) Neither BFS nor DFS
10. How does BFS handle cycles in a graph?
(A) It ignores cycles
(B) It gets stuck in an infinite loop
(C) It marks visited nodes
(D) It does not work with cycles
11. What is the time complexity of BFS on a graph with V vertices and E edges?
(A) O(V)
(B) O(E)
(C) O(V + E)
(D) O(V * E)
12. What is the time complexity of DFS on a graph with V vertices and E edges?
(A) O(V)
(B) O(E)
(C) O(V + E)
(D) O(V * E)
13. Which traversal method is more memory-efficient for wide graphs?
(A) DFS
(B) BFS
(C) Both have the same efficiency
(D) None of the above
14. What is the space complexity of BFS?
(A) O(V)
(B) O(E)
(C) O(V + E)
(D) O(1)
15. Which algorithm can be implemented using DFS?
(A) Topological sorting
(B) Prim’s algorithm
(C) Dijkstra’s algorithm
(D) Kruskal’s algorithm
16. Which algorithm can be implemented using BFS?
(A) Finding connected components
(B) Topological sorting
(C) Shortest path in unweighted graphs
(D) Minimum spanning tree
17. What is the initial step in a BFS traversal?
(A) Mark all nodes as unvisited
(B) Push the starting node onto the stack
(C) Enqueue the starting node
(D) Start from the deepest node
18. What is the initial step in a DFS traversal?
(A) Mark all nodes as unvisited
(B) Push the starting node onto the queue
(C) Enqueue the starting node
(D) Start from the root node
19. In DFS, what happens when a node has no unvisited neighbors?
(A) It stops traversing
(B) It backtracks to the last visited node
(C) It enqueues all neighbors
(D) It visits all nodes in the graph
20. What is a possible output of BFS on a tree structure?
(A) Left-to-right traversal
(B) Top-to-bottom traversal
(C) Random order
(D) Depth-based traversal