Graph Traversal
Graph Traversal MCQs
💠 Graph Traversals – GATE-Level MCQs (Algorithms)
Q1. Breadth-First Search (BFS) uses which data structure?
A) Stack B) Queue C) Priority Queue D) Deque
✅ Answer: B
Explanation: BFS explores neighbors level by level using a queue.
Q2. Depth-First Search (DFS) uses which data structure?
A) Queue B) Stack C) Heap D) Deque
✅ Answer: B
Explanation: DFS explores depth-wise using recursion or explicit stack.
Q3. Time complexity of BFS using adjacency list is:
A) O(V + E) B) O(V²) C) O(E log V) D) O(V log E)
✅ Answer: A
Explanation: Each vertex and edge visited once → O(V + E).
Q4. DFS time complexity for adjacency matrix representation is:
A) O(V²) B) O(V + E) C) O(E log V) D) O(V log E)
✅ Answer: A
Explanation: Checking adjacency for each vertex costs O(V²).
Q5. In BFS, the shortest path in an unweighted graph is found because:
A) It explores by depth
B) It explores by increasing distance
C) It uses stack
D) It backtracks frequently
✅ Answer: B
Explanation: BFS explores nodes in order of non-decreasing distance from the source.
Q6. DFS tree of a directed acyclic graph (DAG) is always:
A) A forest B) A single tree C) A cycle D) Complete graph
✅ Answer: A
Explanation: DAG may be disconnected → DFS gives a forest.
Q7. Which traversal can be used to detect cycles in a directed graph?
A) DFS B) BFS C) Both D) None
✅ Answer: A
Explanation: Back edges in DFS indicate cycles.
Q8. BFS of a disconnected undirected graph:
A) Visits only connected component B) Visits all nodes
C) Always fails D) Requires DFS
✅ Answer: A
Explanation: BFS from one node covers only its connected component.
Q9. Space complexity of BFS is:
A) O(V) B) O(E) C) O(V + E) D) O(V²)
✅ Answer: A
Explanation: Queue can hold up to all vertices at a level.
Q10. Which traversal is best to find connected components in undirected graph?
A) DFS B) BFS C) Both D) None
✅ Answer: C
Explanation: Either DFS or BFS can identify connected components.
Q11. DFS on a graph with V vertices and E edges requires how much space?
A) O(V) B) O(V + E) C) O(E) D) O(V²)
✅ Answer: A
Explanation: Stack depth ≤ V.
Q12. BFS tree of an undirected graph is unique if:
A) Graph is connected
B) Graph is tree
C) Graph is complete
D) Start node is isolated
✅ Answer: B
Explanation: Tree structure ensures unique traversal.
Q13. DFS is particularly useful for:
A) Finding shortest paths
B) Topological sorting
C) Minimum spanning tree
D) Dijkstra’s algorithm
✅ Answer: B
Explanation: Topological sorting uses post-order DFS.
Q14. In BFS, the level of a vertex equals:
A) Its distance from source
B) Its degree
C) Its finish time
D) Its weight
✅ Answer: A
Explanation: BFS visits nodes level-wise → level = distance.
Q15. DFS on a tree will visit each node:
A) Once B) Twice C) n² times D) Randomly
✅ Answer: A
Explanation: Each node visited exactly once.
Q16. Edge classification in DFS includes all except:
A) Tree edge B) Back edge C) Cross edge D) Symmetric edge
✅ Answer: D
Explanation: “Symmetric edge” not part of DFS classification.
Q17. BFS cannot be used directly for:
A) Shortest path (unweighted) B) Detecting bipartite graph C) Detecting cycles in directed graph D) Level-order traversal
✅ Answer: C
Explanation: DFS is better for directed cycle detection.
Q18. A directed acyclic graph (DAG) will have:
A) Back edges B) Tree edges only C) Forward and cross edges D) No edges
✅ Answer: C
Explanation: DAG has no back edges but may have forward/cross edges.
Q19. In BFS, if a vertex is discovered at level k, then all its neighbors are at level:
A) k + 1 B) k C) ≤ k D) ≥ k + 1
✅ Answer: A
Explanation: BFS explores one level deeper next.
Q20. DFS can detect cycles because:
A) Uses stack B) Uses queue
C) Back edges appear only in cyclic paths
D) Uses adjacency matrix
✅ Answer: C
Explanation: Back edges imply cycles.
Q21. Topological sorting is possible only if:
A) Graph is connected B) Graph is DAG C) Graph has cycles D) Graph is tree
✅ Answer: B
Explanation: Topological sort valid only for DAGs.
Q22. BFS traversal of a tree and level-order traversal:
A) Are different
B) Are identical
C) May differ depending on weights
D) Depend on recursion
✅ Answer: B
Explanation: Both visit nodes level by level.
Q23. DFS traversal can be implemented using:
A) Recursion B) Explicit stack C) Both D) None
✅ Answer: C
Explanation: Both recursive and iterative versions possible.
Q24. BFS on an adjacency matrix requires:
A) O(V²) B) O(V + E) C) O(V log V) D) O(E log V)
✅ Answer: A
Explanation: Checking adjacency row takes O(V) per vertex.
Q25. For connected undirected graph, number of BFS trees = ?
A) Depends on start vertex
B) One C) Equal to number of vertices
D) Infinite
✅ Answer: C
Explanation: One BFS tree per source vertex.
Q26. Finish time in DFS is used in:
A) Kruskal’s algorithm B) Dijkstra’s algorithm C) Topological sort D) Prim’s algorithm
✅ Answer: C
Explanation: Sorting vertices by finish time gives topological order.
Q27. BFS fails to detect cycles because:
A) It ignores back edges
B) It marks visited nodes early
C) It explores in breadth-first manner
D) All of these
✅ Answer: D
Explanation: BFS doesn’t maintain recursion info → misses back edges.
Q28. Time complexity to find connected components using DFS:
A) O(V + E) B) O(V²) C) O(V log V) D) O(E²)
✅ Answer: A
Explanation: Every vertex & edge processed once.
Q29. DFS pre-order and post-order can differ because:
A) They depend on edge order
B) They are identical
C) Graph is directed
D) Graph is cyclic
✅ Answer: A
Explanation: The order of adjacency traversal changes visit order.
Q30. In BFS, if two vertices are at same level, then:
A) Equal distance from source B) Different distance C) One is ancestor of other D) Undefined
✅ Answer: A
Explanation: Level represents distance in unweighted graph.
(Skipping repetitive intros — continuing compactly but detailed)
Q31. DFS traversal of a disconnected graph gives: A) One tree B) Forest C) Cycle D) Line
✅ Answer: B — Each component → separate DFS tree.
Q32. BFS traversal order depends on: A) Edge weights B) Queue order C) Graph shape only D) Vertex colors
✅ Answer: B — FIFO order affects visitation.
Q33. DFS can be used to find: A) Strongly connected components B) Minimum path C) MST D) Degree of vertex
✅ Answer: A — Kosaraju’s algorithm uses DFS twice.
Q34. BFS can detect bipartite graph by: A) Level parity coloring B) Stack C) Edge weight check D) Sorting edges
✅ Answer: A — Alternate colors on levels.
Q35. DFS is tail-recursive when: A) Graph is tree B) No branching C) Graph cyclic D) Weighted
✅ Answer: B — Linear chain → tail recursion.
Q36. For DAG, topological sort count equals: A) 1 B) V! C) May vary D) 2
✅ Answer: C — Depends on DAG structure.
Q37. Cycle detection in undirected graph uses: A) Parent check B) Queue size C) Degree check D) BFS only
✅ Answer: A — Edge to visited ≠ parent → cycle.
Q38. BFS can be used to find shortest path in: A) Weighted graphs B) Unweighted graphs C) Directed acyclic graphs D) Negative weighted graphs
✅ Answer: B — BFS works only on unweighted.
Q39. In DFS, if no back edges exist → graph is: A) Acyclic B) Bipartite C) Weighted D) Disconnected
✅ Answer: A — No back edge ⇒ acyclic.
Q40. BFS queue length is maximum when: A) Graph complete B) Graph tree C) Graph chain D) Star graph
✅ Answer: D — Center connected to all leaves.
Q41. DFS recursion depth for binary tree = height → O(log n).
✅ Answer: A
Explanation: For balanced tree.
Q42. Number of edges in BFS tree = V–1 (if connected).
✅ Answer: A
Explanation: Spanning tree has V–1 edges.
Q43. BFS complexity on dense graph = O(V²).
✅ Answer: A
Explanation: E≈V².
Q44. DFS visited array avoids: revisiting nodes → prevents infinite recursion.
✅ Answer: A
Q45. BFS can compute shortest distance table → O(V + E).
✅ Answer: A
Q46. In DAG, forward edges exist but not back edges.
✅ Answer: A
Q47. DFS discovery time < finish time always true.
✅ Answer: A
Q48. Cross edges occur in DFS when: different branches connect.
✅ Answer: A
Q49. BFS traversal on binary tree → Level order traversal.
✅ Answer: A
Q50. DFS traversal on binary tree → Preorder traversal if process before recursion.
✅ Answer: A
Graph Traversal MCQs
Q51. In a DFS traversal of a graph with 10 vertices and no back edges, the graph must be:
A) Cyclic B) Directed C) A forest D) Strongly connected
✅ Answer: C
Explanation: Absence of back edges indicates acyclic structure → forest.
Q52. BFS traversal of a graph is equivalent to:
A) Level order traversal of tree B) Preorder C) Inorder D) Postorder
✅ Answer: A
Explanation: BFS explores level by level like level-order traversal.
Q53. DFS traversal can be implemented using:
A) Queue B) Stack C) Priority queue D) Linked list only
✅ Answer: B
Explanation: DFS uses a stack (explicit or recursion).
Q54. BFS is preferable over DFS when:
A) Searching for shortest path B) Searching deep paths C) Detecting cycles D) Finding articulation points
✅ Answer: A
Explanation: BFS finds shortest path in unweighted graphs.
Q55. Time complexity of DFS for adjacency list representation = ?
A) O(V) B) O(V + E) C) O(V²) D) O(E log V)
✅ Answer: B
Explanation: Each vertex and edge visited once.
Q56. In DFS traversal, a back edge indicates:
A) Cycle B) Self loop only C) Bridge D) Bipartiteness
✅ Answer: A
Explanation: Back edge to ancestor implies cycle.
Q57. BFS traversal is not suitable for:
A) Shortest path in unweighted graphs B) Shortest path in weighted graphs C) Level order search D) Connectivity testing
✅ Answer: B
Explanation: Weighted graphs need Dijkstra, not BFS.
Q58. Number of BFS trees in disconnected graph = ?
A) 1 B) Equal to connected components C) Equal to edges D) Equal to vertices
✅ Answer: B
Explanation: Each component produces its own BFS tree.
Q59. A directed acyclic graph (DAG) has how many possible topological orderings?
A) Always 1 B) May have multiple C) None D) Equal to vertices
✅ Answer: B
Explanation: Different valid orders possible depending on dependencies.
Q60. DFS in undirected graph marks an edge as tree edge if:
A) It leads to unvisited vertex B) Leads to parent C) Leads to ancestor D) Leads to visited vertex
✅ Answer: A
Explanation: First visit to vertex creates tree edge.
Q61. DFS traversal of disconnected graph requires:
A) One DFS B) Separate DFS for each component C) BFS traversal first D) Cycle removal
✅ Answer: B
Explanation: Each disconnected component must be visited separately.
Q62. Edge classification is applicable in:
A) Directed graphs only B) Undirected graphs only C) Trees D) Bipartite graphs
✅ Answer: A
Explanation: DFS edge classification (tree, back, forward, cross) applies only to directed graphs.
Q63. The color method in DFS uses three colors for marking states as:
A) White, Gray, Black B) Red, Green, Blue C) 0, 1, 2 D) A, B, C
✅ Answer: A
Explanation: White = unvisited, Gray = visiting, Black = visited.
Q64. BFS queue can hold at most how many vertices at a time (worst case)?
A) O(V) B) O(E) C) O(V²) D) O(log V)
✅ Answer: A
Explanation: Entire level may be enqueued.
Q65. Which traversal uses implicit recursion stack?
A) BFS B) DFS C) Dijkstra D) Bellman-Ford
✅ Answer: B
Explanation: DFS recursion uses call stack.
Q66. Topological sorting is possible only when graph is:
A) Acyclic B) Cyclic C) Weighted D) Strongly connected
✅ Answer: A
Explanation: Cycles prevent topological order.
Q67. Detecting cycle in directed graph can be done by:
A) BFS only B) DFS only C) Dijkstra D) Prim’s algorithm
✅ Answer: B
Explanation: DFS with recursion stack detects cycles.
Q68. A BFS traversal of a connected undirected graph with n vertices and n edges will have:
A) Exactly one cycle B) No cycle C) Two cycles D) Multiple cycles
✅ Answer: A
Explanation: n vertices and n edges ⇒ one cycle.
Q69. DFS can be used to compute finishing times used in:
A) Topological sort B) BFS C) Dijkstra D) Kruskal
✅ Answer: A
Explanation: DFS finishing times define topological order.
Q70. The space complexity of BFS = ?
A) O(V) B) O(V + E) C) O(E) D) O(log V)
✅ Answer: A
Explanation: Queue can store O(V) vertices.
Q71. DFS tree of an undirected graph has 20 vertices and 19 edges. Graph is:
A) Connected and acyclic B) Disconnected C) Cyclic D) Complete
✅ Answer: A
Explanation: n-1 edges → tree → connected, acyclic.
Q72. The postorder numbering in DFS is mainly used to:
A) Detect cycles B) Classify edges C) Compute SCCs D) Sort edges
✅ Answer: C
Explanation: Kosaraju’s algorithm uses postorder for SCCs.
Q73. In DFS traversal, discovery time and finishing time differ by:
A) Constant B) Proportional to degree C) 2 × subtree size D) None
✅ Answer: C
Explanation: Each vertex adds two timestamps (entry, exit).
Q74. Number of edges explored in BFS = ?
A) E B) 2E C) V D) V + E
✅ Answer: A
Explanation: Each edge considered once per direction.
Q75. BFS can be used to detect bipartite graphs by:
A) Level coloring B) DFS C) Counting edges D) Sorting degrees
✅ Answer: A
Explanation: Alternate coloring levels ensures no same-color adjacency.
Q76. DFS traversal order depends on:
A) Adjacency list order B) Vertex degree C) Graph type D) None
✅ Answer: A
Explanation: Different adjacency orders → different DFS trees.
Q77. In BFS, when is a node marked as visited?
A) When dequeued B) When enqueued C) When processed D) After traversal
✅ Answer: B
Explanation: Marking on enqueue avoids duplication.
Q78. Which traversal can be used to find strongly connected components?
A) BFS B) DFS C) Dijkstra D) Kruskal
✅ Answer: B
Explanation: DFS-based algorithms (Kosaraju, Tarjan).
Q79. BFS traversal of tree starting from root visits nodes in:
A) Preorder B) Inorder C) Level order D) Postorder
✅ Answer: C
Explanation: BFS = level order traversal.
Q80. For an undirected connected graph, DFS traversal gives a spanning:
A) Tree B) Forest C) DAG D) Cycle
✅ Answer: A
Explanation: DFS on connected graph yields a spanning tree.
Q81. BFS traversal can be applied to:
A) Directed B) Undirected C) Both D) None
✅ Answer: C
Explanation: BFS works on any graph type.
Q82. Recursive DFS uses which data structure internally?
A) Stack B) Queue C) Priority Queue D) Deque
✅ Answer: A
Explanation: Recursion uses call stack.
Q83. Topological sort of DAG using DFS has time complexity:
A) O(V + E) B) O(V²) C) O(E log V) D) O(VE)
✅ Answer: A
Explanation: Each vertex and edge visited once.
Q84. BFS is not recursive because:
A) Uses queue B) Uses stack C) Cannot detect cycles D) Complex logic
✅ Answer: A
Explanation: Queue prevents recursion.
Q85. BFS traversal produces shortest paths when:
A) Edge weights equal B) Edge weights positive C) Edge weights negative D) Graph cyclic
✅ Answer: A
Explanation: Equal weight edges → BFS gives shortest paths.
Q86. DFS traversal can be used to detect bridges using:
A) Discovery and low times B) Level numbers C) Edge weights D) In-degrees
✅ Answer: A
Explanation: Tarjan’s algorithm uses low values for bridges.
Q87. BFS traversal can fail to terminate if:
A) No visited array used B) Recursion used C) Stack overflow D) Edges missing
✅ Answer: A
Explanation: Without marking, nodes re-enqueued infinitely.
Q88. DFS traversal number of recursive calls = ?
A) V B) E C) V + E D) 2V
✅ Answer: A
Explanation: One call per vertex.
Q89. In directed acyclic graph, the reverse postorder of DFS = ?
A) Topological order B) BFS order C) Random D) Level order
✅ Answer: A
Explanation: Reverse of finishing time gives topo order.
Q90. BFS traversal tree edges correspond to:
A) First discovery of vertices B) Back edges C) Cross edges D) Forward edges
✅ Answer: A
Explanation: Each first visit creates tree edge.
Q91. DFS traversal of complete graph with n vertices visits:
A) All vertices once B) Multiple visits C) None D) Random subset
✅ Answer: A
Explanation: DFS ensures each vertex visited exactly once.
Q92. If DFS of graph with 6 vertices finishes with vertex 1 first, it means:
A) 1 has no outgoing edges B) 1 is source C) 1 is sink D) 1 has max degree
✅ Answer: C
Explanation: Finishes first → no outgoing edges.
Q93. BFS traversal detects cycle when:
A) Edge connects two visited vertices in same level B) Edge connects to unvisited vertex C) Self-loop D) Forward edge
✅ Answer: A
Explanation: Same-level visited vertex indicates cycle.
Q94. For an undirected tree with n vertices, BFS traverses how many edges?
A) n – 1 B) n C) 2n D) log n
✅ Answer: A
Explanation: Tree has n–1 edges.
Q95. DFS traversal of disconnected graph produces:
A) Forest B) Single tree C) Cyclic subgraph D) None
✅ Answer: A
Explanation: Each component → one DFS tree.
Q96. BFS traversal uses which visiting pattern?
A) FIFO B) LIFO C) Random D) Priority
✅ Answer: A
Explanation: Queue → FIFO.
Q97. DFS traversal uses which visiting pattern?
A) LIFO B) FIFO C) Random D) Round robin
✅ Answer: A
Explanation: Stack → LIFO.
Q98. BFS traversal starting from vertex u can reach vertex v iff:
A) v is in same component B) v has higher degree C) v is isolated D) v has lower degree
✅ Answer: A
Explanation: BFS explores connected component of start vertex.
Q99. Topological sort exists iff graph has:
A) No cycle B) Equal vertices and edges C) One sink D) Equal in/out degrees
✅ Answer: A
Explanation: DAG ⇒ topological order possible.
Q100. DFS traversal of a tree visits every vertex exactly:
A) Once B) Twice C) Thrice D) Four times
✅ Answer: A
Explanation: Each vertex entered once and exited once.
About the Author
