QUESTION 27 Which of the statement(s) given below is/are correct?

Statement I is incorrect: DFS visits each vertex exactly once in a properly implemented algorithm using a visited set. The starting vertex is not visited twice. Statement II is correct: BFS uses a queue and marks nodes as visited upon discovery, ensuring each node is processed exactly once. Therefore, only statement II is correct.

Step-by-step Derivation:
Analyzing each statement:

Statement I: DFS visits the starting vertex twice

• False. In standard DFS implementation, we mark a vertex as visited when we first encounter it and never revisit it.
• Pseudocode: mark vertex as visited → process it → recursively visit unvisited neighbors
• Each vertex is visited exactly once, not twice.
• Exception: If implementing DFS with explicit entry/exit times or discovery/finish times for analysis purposes, we might record times twice (upon entry and exit), but we don't "visit" it twice in the traversal sense.

Statement II: BFS visits each node just one time

• True. BFS uses a queue and a visited set.
• Pseudocode: enqueue starting node → mark as visited → while queue not empty: dequeue, process, enqueue unvisited neighbors (mark them as visited immediately)
• Once a node is marked visited, it won't be enqueued again, ensuring exactly one visit per node.

Conclusion: Only Statement II is correct → Answer is D